Двоичная функция Haskell (карта)

Question

Как определить функцию Haskell, которая будет применять функцию к каждому значению в двоичном дереве? Итак, я знаю, что это похоже на функцию map - и что ее тип будет:

mapT :: (a -> b) -> Tree a -> Tree b

Но вот и все ...

Answer 1

Вы можете объявить экземпляр класса Functor. Это стандартный класс для типов данных, которые позволяют отображать функцию. Обратите внимание, насколько тип fmap похож на тип mapT:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Давайте предположим, что ваше дерево определено как

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

Затем вы можете объявить экземпляр Functor следующим образом:

instance Functor Tree where
  fmap f (Node l r) = Node (fmap f l) (fmap f r)
  fmap f (Leaf x) = Leaf (f x)

Вот как это можно использовать:

main = do
  let t = Node (Node (Leaf 1) (Leaf 2)) (Leaf 3)
  let f = show . (2^)
  putStrLn $ "Old Tree: " ++ (show t)
  putStrLn $ "New Tree: " ++ (show . fmap f $ t)

Выход:

Old Tree: Node (Node (Leaf 1) (Leaf 2)) (Leaf 3)
New Tree: Node (Node (Leaf "2") (Leaf "4")) (Leaf "8")

Вы также можете определить для удобства:

mapT = fmap

Конечно, вы можете делать это без классов типов, но это делает код более читабельным для других, если вы используете стандартные функции (все знают обычное поведение fmap).

Answer 2

Я буду притворяться, что это домашнее задание, и не выдам весь ответ. Если я ошибаюсь, мои извинения.

Вероятно, ваш Tree тип выглядит примерно так:

data Tree a = TreeNode a (Tree a) (Tree a) | EmptyNode

Здесь есть два случая, и вам нужно написать mapT реализацию для каждого из них:

• Внутренний узел TreeNode, который имеет значение типа a и имеет левого и правого дочернего элемента. Что нужно сделать в этом случае?
• Терминальный узел, EmptyNode. Что нужно сделать в этом случае?

Answer 3

Базовый формат функции карты применяется к обоим.Давайте посмотрим на определение функции карты для списков:

map f (x:xs) = f x : map f xs
map _ []     = []

Мы можем обобщить это так:

1. Вы берете первое значение в структуре данных
2. Примените к ней функцию
3. Рекурсивно вызовите функцию вашей карты с остатком структуры данных
4. Передайте и модифицированное значение, и рекурсивный вызов в конструктор для вашего типа.
5. Когда вы дойдете до конца, прекратите повторение

Все, что вам действительно нужно, это посмотреть на конструктор, и функция карты должна встать на свои места.

Answer 4

Интересный вопрос, если входные и выходные данные должны быть отсортированы двоичные деревья. Если вы просто наивно обходите дерево и применяете функцию, выходное дерево больше не может быть отсортировано. Например, рассмотрим, является ли функция нелинейной, например

f(x) = x * x - 3 * x + 2

Если вход имеет {1, 2, 3, 4}, то выход будет иметь {2, 0, 0, 2}. Должно ли выходное дерево содержать только 0 и 2?

Если это так, вам может понадобиться итеративное построение выходного дерева по мере его усечения и обработки входного дерева.