Haskell任意深度的递归HashMap数据结构

有了这个Python函数:

def mut_add_to_tree(text, tree):
    tree_ = tree
    for i, c in enumerate(text):
        if c in tree_:
            tree_[c][0] += 1
            tree_ = tree_[c][1]
        else:
            for c_ in text[i:]:
                tree_[c_] = [1, {}]
                tree_ = tree_[c_][1]
            break

创建嵌套dicts的数据结构,如下所示:

In [15]: tree = {}                                                                             

In [16]: mut_add_to_tree("cat", tree)                                                          

In [17]: tree                                                                                  
Out[17]: {'c': [1, {'a': [1, {'t': [1, {}]}]}]}

In [18]: mut_add_to_tree("car", tree)                                                          

In [19]: tree                                                                                  
Out[19]: {'c': [2, {'a': [2, {'t': [1, {}], 'r': [1, {}]}]}]}

In [20]: mut_add_to_tree("bat", tree)                                                          

In [21]: tree                                                                                  
Out[21]: 
{'c': [2, {'a': [2, {'t': [1, {}], 'r': [1, {}]}]}],
 'b': [1, {'a': [1, {'t': [1, {}]}]}]}

In [22]: mut_add_to_tree("bar", tree)                                                          

In [23]: tree                                                                                  
Out[23]: 
{'c': [2, {'a': [2, {'t': [1, {}], 'r': [1, {}]}]}],
 'b': [2, {'a': [2, {'t': [1, {}], 'r': [1, {}]}]}]}

如何在Haskell中复制此行为？更一般地说,如何创建和插入任意深度的嵌套HashMaps？

我试验过以下内容:

type NestedHashMap k v = HashMap Char (Int,(HashMap Char v))

toNestedHashMap :: String -> HashMap Char (Int, HashMap Char v)
toNestedHashMap [] = fromList []
toNestedHashMap (x:xs) = fromList [(x, (1, toNestedHashMap xs))]

但已经在这里,编译器告诉我

Couldn't match type ‘v’ with ‘(Int, HashMap Char v0)’
      ‘v’ is a rigid type variable bound by
        the type signature for:
          toNestedHashMap :: forall v.
                             String -> HashMap Char (Int, HashMap Char v)
        at WordFuncs.hs:48:1-63
      Expected type: HashMap Char (Int, HashMap Char v)
        Actual type: HashMap
                       Char (Int, HashMap Char (Int, HashMap Char v0))

任何帮助赞赏.谢谢.

这基本上是一种无限类型.Map Char (Int, Map Char (Int, Map Char (... ¿()?)...)))是类型同义词必须展开的,以允许你在Python中做的事情.

Haskell本身不允许无限类型,但它确实允许您创建这种类型的结构.为此,创建一个类型同义词是不够的,你需要一个newtype,在这种情况下意味着对编译器"我不应该费心去复制它,它是一个已经被检查的已知,可区分的类型".

newtype NestedHashMap k v = NestedHashMap  -- N.B. the `v` argument is unused
   { getNestedHashMap :: HashMap k (Int, NestedHashMap k v) }

toNestedHashMap :: String -> NestedHashMap Char ()
toNestedHashMap [] = NestedHashMap $ fromList []
toNestedHashMap (x:xs) = NestedHashMap $ fromList [(x, (1, toNestedHashMap xs))]