2013-01-30 1 views
1

Я хочу, чтобы структура данных Trie была складной. Основная структура данных выглядит следующим образом:Реализация Складная для Trie

data Trie a = Trie { 
    value :: Maybe a, 
    children :: [(Char, Trie a)] 
} deriving (Show) 

Я пытался реализовать Складная класс путем определения foldr:

instance F.Foldable Trie where 
    foldr f z (Trie (Just v) children) = 
     F.foldr (\a b -> F.foldr f b a) (f v z) children 

    foldr f z (Trie Nothing children) = 
     F.foldr (\a b -> F.foldr f b a) z children 

Это не компилируется с этой ошибкой:

Couldn't match type `a' with `Trie a' 
    `a' is a rigid type variable bound by 
     the type signature for foldr :: (a -> b -> b) -> b -> Trie a -> b 
     at Trie.hs:17:5 
Expected type: [(Char, a)] 
    Actual type: [(Char, Trie a)] 
In the third argument of `F.foldr', namely `children' 
In the expression: 
    F.foldr (\ a b -> F.foldr f b a) (f v z) children 

Однако, если я изменил тип детей на Map Char (Trie a), реализация Foldable будет работать без изменений. Я хотел бы сохранить список ассоциаций для простоты в данный момент. Не могли бы вы объяснить мне, почему foldr ведет себя по-разному на карте и списке ассоциаций?

+1

Поскольку '[]' 'Foldable' экземпляра 's не один вы хотите, если все списки были списки ассоциаций. –

+0

Не могли бы вы рассказать об этом? Это в основном моя попытка узнать о системе типов. – passy

+0

Когда вы создаете экземпляр 'foldr' в типе списка' [(a, b)] ', он будет работать с кортежами типа' (a, b) ', тогда как если бы вы хотели думать обо всех списках как списки ассоциаций, вы может ожидать, что 'foldr' будет работать только на части value,' ''. Это именно то, что происходит, когда вы создаете экземпляр 'foldr' на карте типа« Карта a b »: он работает только на' b's. –

ответ

3

Ошибка заключается в том, что вы пытаетесь сбросить список значений ключа , а не список Trie. То, что вы хотите сделать, это игнорировать Char ключи и только раз в каждую из дочерних узлов, как так

foldr f z (Trie (Just v) children) = 
    F.foldr (\(_, a) b -> F.foldr f b a) (f v z) children 

foldr f z (Trie Nothing children) = 
    F.foldr (\(_, a) b -> F.foldr f b a) z children 
+0

Фантастический! Спасибо за быстрый ответ. Я фокусировался на типе детей, а не на определении функции. – passy