Я хочу, чтобы структура данных 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 ведет себя по-разному на карте и списке ассоциаций?
Поскольку '[]' 'Foldable' экземпляра 's не один вы хотите, если все списки были списки ассоциаций. –
Не могли бы вы рассказать об этом? Это в основном моя попытка узнать о системе типов. – passy
Когда вы создаете экземпляр 'foldr' в типе списка' [(a, b)] ', он будет работать с кортежами типа' (a, b) ', тогда как если бы вы хотели думать обо всех списках как списки ассоциаций, вы может ожидать, что 'foldr' будет работать только на части value,' ''. Это именно то, что происходит, когда вы создаете экземпляр 'foldr' на карте типа« Карта a b »: он работает только на' b's. –