Functional map-like data structure with arbitrary length data as keys?

It could very well be that the answer to this question is an obvious and resounding "there's no such thing", but I'll give it a shot: Is there a functional map-like data structure that is more efficient than a standard map when the keys have an arbitrary, often very big, size?

For the sake of concreteness, consider the Haskell type

(Ord k) => Map [k] v

in which lookups can take a very long time if lists need to be compared down to a deep level. I guess hashing is also out of the question due to the arbitrary length of the lists. I still can't help but 开发者_如何学Cthink there could be a clever data structure out there.

Is hashing out of the question? There's no prefix of the key structure that can be computed efficiently?

If not, how about a hashmap? Take the very big key, reduce it to something very small, use that as an index into a structure.

• hashmap on Hackage.
• Johan Tibbel's talk on hash tree structures

A trie?

If you have two long keys that are almost identical, a Map will compare them both from the beginning, but a trie will only compare the suffixes that haven't already been eliminated by previous comparisons (if you see what I mean). So a trie would be more time-efficient in that situation.

Tries can be optimised in various ways, and you might also want to look at ternary trees.

Here's one:

module ListMap where
import Data.Map as M

data ListMap k v = ListMap { ifEmpty :: Maybe v, ifFull :: Maybe k (ListMap k v) }

empty :: ListMap k v
empty = ListMap Nothing M.empty

singleton :: [k] -> v -> ListMap k v
singleton [] v = ListMap.empty { ifEmpty = Just v }
singleton (k:ks) v = ListMap.empty { ifFull = M.singleton k (ListMap.singleton ks v) }

lookup :: Ord k => [k] -> ListMap k v -> Maybe v
lookup [] lm = ifEmpty lm
lookup (k:ks) lm = M.lookup k (ifFull lm) >>= ListMap.lookup ks

insert :: Ord k => [k] -> v -> ListMap k v -> ListMap k v
insert [] v lm = lm { ifEmpty = Just v }
insert (k:ks) v lm = lm { ifFull = M.alter (Just . insertion) k (ifFull lm) }
  where insertion = maybe (ListMap.singleton ks v) (ListMap.insert ks v)

It's essentially creating a prefix tree on the list elements so you only compare as far as necessary.