Реализация haskell mapTree с использованием foldTree

Question

Этот код из задания, которое я уже решил.Тем не менее я пытаюсь выяснить, смогу ли я исправить свою первоначальную попытку.

Итак, мы получили эту древовидную структуру и функцию foldTree.

data Tree a = Leaf a
 | Node (Tree a) (Tree a)

foldTree :: (b -> b -> b) -> (a -> b) ->  Tree a -> b
foldTree op f (Leaf x)  = f x
foldTree op f (Node l r) = foldTree op f l `op` foldTree op f r

Теперь mapTree должен быть реализован с использованием foldTree.Я сделал это следующим образом.

 mapTree :: (a -> b) -> Tree a -> Tree b
 mapTree' f tree = foldTree Node (Leaf . f) tree

То, что я изначально придумал и до сих пор не могу получить на работе, это:

 mapTree :: (a -> b) -> Tree a -> Tree b
 mapTree f tree = foldTree Node transFunc tree 
   where transFunc :: Tree a -> Tree b
         transFunc (Leaf x)    = Leaf (f x)
         transFunc (Node l r)  = Node (transFunc l) (transFunc r)

Answer 1

Вторая функция неверна из-за ее типа: Tree a -> Tree b, в то время как foldTree ожидает, что она будет a -> b, где a взято из Tree a.b требуется для mapTree, чтобы быть Tree b, поэтому третий аргумент для foldTree должен иметь тип a -> Tree b.

Итак, самая простая фиксированная версия вашего transFunc:

mapTree :: forall a b. (a -> b) -> Tree a -> Tree b
mapTree f tree = foldTree Node transFunc tree 
  where transFunc :: a -> Tree b
        transFunc x = Leaf (f x)

Обратите внимание, что вам нужно включить расширение ScopedTypeVariables для его компиляции.

И эта версия transFunc является эквивалентом вашего рабочего решения: (Leaf . f)