以任意长度数据作为键的函数式映射数据结构？

Question

这个问题的答案很可能是一个明显而响亮的“不存在这样的东西”，但我会尝试一下：是否存在一种功能性的类似地图的数据结构，在以下情况下比标准地图更有效：键的大小是任意的，通常非常大？

为了具体起见，请考虑 Haskell 类型，

(Ord k) => Map [k] v

如果列表需要深入比较，查找可能会花费很长时间。我想由于列表的任意长度，散列也是不可能的。我仍然情不自禁地认为可能存在一种聪明的数据结构。

Answer 1

散列是不可能的吗？没有可以高效计算的关键结构的前缀吗？

如果没有，那么哈希图怎么样？将非常大的键减少到非常小的值，将其用作结构的索引。

• Hackage 上的 hashmap。
• Johan Tibbel 关于哈希树结构的演讲

Answer 2

特里树？

如果您有两个几乎相同的长键，则 Map 将从头开始比较它们，但 trie 只会比较先前比较中尚未消除的后缀（如果您明白我的意思）。所以在这种情况下，trie 会更省时。

尝试可以通过多种方式进行优化，您可能还想看看三元树。

Answer 3

这是一个：

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)

它本质上是在列表元素上创建一个前缀树，因此您只需进行必要的比较。