Карта Хаскелла для Деревьев

Question

Мое дерево определяется

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

Я также объявляю дерево тестирования.

myTree = Node (Node (Leaf 1) (Leaf 2)) (Leaf 3)

Я хочу создать функцию maptree f, которая будет работать на Leaf. А точнее, f x = x +1,

тогда maptree f myTree вернется

Node (Node (Leaf 2) (Leaf 3)) (Leaf 4)

Мое решение

maptree f (Leaf a)= Leaf (f a)
maptree f (Node xl xr ) = Node (maptree xl) (maptree xr)

но вернется следующая ошибка

Couldn't match expected type `Tree a'
       against inferred type `Tree t -> Tree t'
Probable cause: `maptree' is applied to too few arguments
In the first argument of `Node', namely `(maptree xl)'
In the expression: Node (maptree xl) (maptree xr)

Сбой, загруженные модули: нет.

Однако, если я сделаю

maptree (Leaf a)= Leaf ( a + 1)
maptree (Node xl xr ) = Node (maptree xl) (maptree xr)

это работает.

Я не вижу разницы между первой функцией и второй. Как я могу получить ошибку? Спасибо.

Answer 1

Вам не хватает функции в рекурсивных вызовах maptree:

maptree f (Leaf a)= Leaf (f a) 
maptree f (Node xl xr ) = Node (maptree xl) (maptree xr)

должно быть

maptree f (Leaf a)= Leaf (f a) 
maptree f (Node xl xr ) = Node (maptree f xl) (maptree f xr)

Answer 2

Обратите внимание, что это очевидный fmap экземпляра Functor для вашего типа Tree. Поэтому вы можете использовать расширение DeriveFunctor, чтобы GHC сгенерировал его для вас.

{-# LANGUAGE DeriveFunctor #-}
data Tree a = Leaf a | Node (Tree a) (Tree a) 
    deriving (Functor, Show)

Давайте попробуем.

*Main> fmap (+1) (Node (Node (Leaf 1) (Leaf 2)) (Leaf 3))
Node (Node (Leaf 2) (Leaf 3)) (Leaf 4)

Answer 3

Сообщение об ошибке в основном говорит вам, что не так: вы не передаете maptree достаточно аргументов.Определение maptree f (Node xl xr) говорит, что maptree принимает два аргумента, функцию и дерево.Но когда вы называете это как maptree xl, вы даете ему только один аргумент (дерево).

Во второй версии вы определили maptree, чтобы он принимал только один аргумент (дерево), поэтому он не приводит к этой ошибке.

Вы можете решить вашу проблемунапример, вызывая maptree f xl вместо maptree xl.

Answer 4

Один тупой способ не забыть передать функцию при более глубокой рекурсии (для такого рода функций более высокого порядка) - использовать помощника:

maptree f (Leaf a)     = Leaf (f a)
maptree f (Node xl xr) = Node (go xl) (go xr)
    where go = maptree f

Или, альтернативно (и, возможно, большеобычно):

maptree f tree = go tree                      -- or eta reduce:   maptree f = go
    where go (Leaf a)     = Leaf (f a)
          go (Node xl xr) = Node (go xl) (go xr)

В первом примере я использую go как макрос для maptree f.Во втором примере я использую тот факт, что вход maptree f находится в области видимости внутри функции go, поскольку go объявлен в предложении where из maptree.