Всем привет.
Познаю хаскель, наткнулся на проблему.
Есть простое дерево с лесом:
data RoseTree a = RoseEmpty | RoseTree a [RoseTree a]
deriving (Show,Eq)
Пытаюсь реализовать для него интерфейс тайпкласса Foldable:
instance Foldable RoseTree where
foldr _ acc RoseEmpty = acc
foldr f acc (RoseTree x []) = f x acc
foldr f acc (RoseTree x ts) = let mapped = map (foldr f acc) ts
folded = foldr f acc mapped
in f x folded
Идея простая: чтобы свернуть список поддеревьев, применяю частично примененный (foldr f acc) к списку, получаю вместо списка поддеревьев (RoseTree a) список значений (a), потом сворачиваю список значений и применяю функцию f к значению ноды из паттерна и свернутому значению поддеревьев.
Но получаю ошибку в ghci:
error:
• Couldn't match type ‘b’ with ‘a’
‘b’ is a rigid type variable bound by
the type signature for:
foldr :: forall a b. (a -> b -> b) -> b -> RoseTree a -> b
at lecture11.hs:131:5
‘a’ is a rigid type variable bound by
the type signature for:
foldr :: forall a b. (a -> b -> b) -> b -> RoseTree a -> b
at lecture11.hs:131:5
Expected type: [a]
Actual type: [b]
• In the third argument of ‘foldr’, namely ‘mapped’
In the expression: foldr f acc mapped
In an equation for ‘folded’: folded = foldr f acc mapped
• Relevant bindings include
folded :: b (bound at lecture11.hs:134:39)
mapped :: [b] (bound at lecture11.hs:133:39)
ts :: [RoseTree a] (bound at lecture11.hs:133:29)
x :: a (bound at lecture11.hs:133:27)
acc :: b (bound at lecture11.hs:133:13)
f :: a -> b -> b (bound at lecture11.hs:133:11)
Насколько я понимаю, ругань на то, что частично примененный (foldr f acc) получает на вход список не того типа. Но не могу понять почему, ведь этот foldr есть мой рекурсивный вызов и по идее он должен выглядеть так:
map (foldr f acc) ts
или для примера
map (foldr (+) 0) [RoseTree 1 [], RoseTree 2 [], RoseTree 3 []]
т.е.
[foldr (+) 0 (RoseTree 1 []), foldr (+) 0 (RoseTree 2 []), foldr (+) 0 (RoseTree 3 [])]
и по одной из моих реализаций Foldable RoseTree, где
foldr f acc (RoseTree x []) = f x acc
, получаем [1, 2, 3], что подтверждается пошаговым биндингом этого кода в ghci, но вот целиком ghci мой Foldable не проглатывает.
В чем проблема, парни?
