Haskell Recursive HashMap data structure of arbitrary depth

Question

With this Python function:

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

is created a data structure of nested dicts like this:

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, {}]}]}]}

How can this behaviour be replicated in Haskell? More generally, how are nested HashMaps of arbitrary depth created and inserted into?

I've experimented with the following:

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))]

but already here the compiler tells me

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))

Any help appreciated. Thanks.

Answer 1

This is basically an infinite type. Map Char (Int, Map Char (Int, Map Char (... ¿()?)...))) is what the type synonym would have to unroll, to allow the stuff you're doing in Python.

Haskell doesn't allow infinite types per se, but it does allow you to create the structure of such a type. For this, it's not sufficient to make a type synonym, you need a newtype, which in this case means to the compiler “I shouldn't bother recursing this, it's a known, distinguishable type that has already been checked”.

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))]