CODEWITHSUNDEEP
data-structureshaskelldictionaryfunctional-programming
gspr
gspr

Reputation: 11227

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 think there could be a clever data structure out there.

Upvotes: 3

Views: 510

Answers (3)

rampion
rampion

Reputation: 89123

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.

Upvotes: 1

Robin Green
Robin Green

Reputation: 33103

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.

Upvotes: 3

Don Stewart
Don Stewart

Reputation: 137997

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.

Upvotes: 6

Related Questions