Haskell Рекурсивная структура данных HashMap произвольной глубины - PullRequest
Новая
       12

Haskell Рекурсивная структура данных HashMap произвольной глубины

0 голосов
/ 06 декабря 2018

С помощью этой функции 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

создается структура данных вложенных диктов, подобная этой: 

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

Любая помощь приветствуется.Спасибо.

1 Ответ

0 голосов
/ 06 декабря 2018

Это в основном бесконечный тип.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))]
...