реализация функции mapTree

Question

Я задан, чтобы определить функцию:

treeMap :: (a -> b) -> BinaryTree a -> BinaryTree b

, который принимает функцию и двоичное дерево и создает двоичное дерево, в котором все узлы являются результатом применения функции к данному дереву

бинарное дерево:

data BinaryTree a = Nil | BNode a (BinaryTree a) (BinaryTree a)

и мой код не соответствует. я получаю ошибку:

error: Not in scope: data constructor ‘BinaryTree’
treeMap f (BNode x (BinaryTree l) (BinaryTree r)) =    |                                    ^^^^^^^^^^

мой код:

data BinaryTree a = Nil | BNode a (BinaryTree a) (BinaryTree a)

treeMap :: (a -> b) -> BinaryTree a -> BinaryTree b
treeMap f Nil  = Nil
treeMap f (BNode x (BinaryTree l) (BinaryTree r)) =
    BNode (f x) (BinaryTree (treeMap f l)) (BinaryTree (treeMap f r))

Answer 1

Ваш шаблон (BNode x (BinaryTree l) (BinaryTree r)) является , а не действительным шаблоном.Действительно, определение данных двоичного дерева гласит:

data BinaryTree a = Nil | <b>BNode a (BinaryTree a) (BinaryTree a)</b>

, что означает, что BNode является конструктором данных , который упаковывает три аргумента. тип из последних двух аргументов равен BinaryTree a, но вы не можете использовать типы при сопоставлении с образцом.

Таким образом, вы должны использовать l и r в качестве переменных для этих параметров.(или вы можете использовать конструкторы данных типа BinaryTree a).

То же самое, когда вы создаете тип BinaryTree a.Вы вызываете конструктор со значениями BNode x l r со значениями x, l и r, типы в выражении здесь не указываются.Вы можете указать типы, но затем используйте оператор ::.

Таким образом, вы можете исправить свой код с помощью:

treeMap :: (a -> b) -> BinaryTree a -> BinaryTree b
treeMap f Nil  = Nil
treeMap f (BNode x <b>l</b> <b>r</b>) = BNode (f x) <b>(treeMap f l)</b> <b>(treeMap f r)</b>

или более элегантно:

treeMap :: (a -> b) -> BinaryTree a -> BinaryTree b
treeMap f = go
    where go Nil = Nil
          go (BNode x l r) = BNode (f x) (go l) (go r)

При этом вы можете ghc получить для вас экземпляр Functor, используя DeriveFunctor pragma:

{-# <b>LANGUAGE DeriveFunctor</b> #-}

data BinaryTree a = Nil | BNode a (BinaryTree a) (BinaryTree a) <b>deriving Functor</b>

treeMap - это всего лишь fmap :: Functor f => (a -> b) -> f a -> f b с f ~ BinaryTree здесь.