карта функции Дерева в Haskell

Question

Мы можем определить бинарное дерево как таковые:

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

Теперь у меня есть функция, скажет (+), как я мог сопоставить это бинарное дерево? Как можно сопоставить произвольную функцию двоичному дереву?
Так (+) a b будет

Node (+) a (Node (+) Empty Empty) (Node a Empty Empty)) 

Это домашнее задание, которое просит нас сопоставить функцию дерева и выше, как я понимаю.
Объявление функции может быть:

functionToTree :: (t1 -> t2) -> Tree a 

Я поднял на определение типа функции которого число аргументов переменной.

EDIT: К сожалению, как сказал nponeccop, я понял свою задачу, и я знал, как писать functionToTree :: (a -> b) -> Tree a -> Tree b. Несмотря на это, мне все еще интересно узнать о моем первоначальном вопросе. Чтобы уточнить немного, вот что я думаю:

     (+) a 
         /\ 
         (+) a 

Что касается функции f принимает три параметра abc:

     f a b 
        / \ 
        f a b 
        /\ 
        f a 

Хорошо, это уже не о моей домашней работе , Я просто задаюсь вопросом, можно ли написать такую ​​функцию. Мы можем определить список таким образом:

data Li a = Cons a (Li a) 
      | Empty 
      deriving (Show, Eq, Order) 

Можно ли определить общую функцию, как это? Если вы думаете, что мой вопрос не имеет смысла, пожалуйста, проголосуйте.

БОЛЬШЕ: Я уточнил свой вопрос. Я думаю, что мое дерево - еще один способ проиллюстрировать частичную функцию и карри.

Answer 1

Вы не очень хорошо поняли задачу. Отображение функции по дереву применяется к каждому элементу данных, содержащемуся в дереве.

Предлагаю вам начать с рисования дерева, содержащего цифры.

   1 
     / \ 
      2  3 
      \ /\ 
      4 6 5 

Вы можете закодировать это дерево, используя тип данных Tree a, то есть, записать дерево как выражение с Node и Empty конструкторами?

Вот некоторые подсказки:

• Верхний узел содержит 1 и два непустых поддеревьев.

• Левое поддеревье содержит 2, одно пустое поддерево и одно непустое поддерево.

• В правом поддереве содержится 3 и два непустых поддеревья.

• Узлы уровня три - это все деревья с пустыми поддеревьями.

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

Вы нарисовали свое дерево неправильно. Правильное дерево:

   f 1 
      / \ 
     f 2  f 3 
      \ / \ 
      f 4 f 6 f 5 

Таким образом, вы можете отображать функции только с одним аргументом, но не с двумя, тремя или более.

Идея состоит в том, что вы можете (например) добавить два к каждому элементу дерева. Поэтому, если вы пройдете

   1 
     / \ 
      2  3   and (\x -> x + 2) or equivalently (+2) 
      \ /\ 
      4 6 5 

к вашей функции, например. tree2 = functionToTree (+2) tree1, вы получите обратно исправленный дерево:

   3 
     / \ 
      4  5 
      \ /\ 
      6 8 7 

Таким образом, каждый элемент дерева заменяется новым элементом.

Answer 2

Учитывая функциональную структуру данных (в данном случае, дерево), обычно вы можете сделать с ней две общие вещи.

1. карта
2. складка

Mapping где вы берете функцию f :: a -> b и структуру origTree :: Tree a и применить функцию к элементам конструкции, в результате чего newTree :: Tree b. (Заметим, что канонический способ сделать структуру назначаемыми, чтобы сделать его Functor, и определить fmap)

Складные где вы как-то соединение всех элементов структуры в какой-то новое значение. Когда вы сказали, что у вас есть Tree и функция (+), я сразу же подумал о сгибе: суммируя все элементы в дереве. (Заметим, что канонический способ сделать структуру Складная, чтобы сделать его экземпляр Foldable (сюрприз!) И определить foldMap или foldr)

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

---

Теперь, касаясь вашего собственного вопроса, превращая функцию в дерево. Немного непонятно, что именно вы имеете в виду, поставив a, b и c в свое дерево, но давайте немного поиграем с этой идеей. Для простоты я не собираюсь делать полностью общую функцию. Кроме того, поскольку ваши функции «деревья» довольно однобокие, я называю их FunHistory вместо Tree. Это будет представлять историю приложений функций.

data FunHistory a b = Result b (FunHistory a b) 
        | Application (a -> FunHistory a b) a (FunHistory a b) 
        | Base (a -> FunHistory a b) 

Теперь этот тип немного странный.Result содержит результат типа b, а также ссылку на предыдущий история применения функций. Base содержит функцию с no история функциональных приложений и возможность , производя будущую историю, если предоставляется значение типа a. Таким образом, Application является промежуточной записью, которая обеспечивает возможность создания будущей истории, а также отмечает прошлую историю и значение которой было применено к этой прошлой истории.

Теперь давайте сделаем некоторые функции для удобства. Ремень на ремне безопасности, это может стать ухабистым.

mkHist :: (a -> b) -> FunHistory a b 
mkHist f = let h = Base (\x -> Result (f x) h) in h 

Учитывая функцию с одним аргументом, мы можем создать историю из нее магией. Этот особый аромат магии называется «лень» и «рекурсивный пусть».

Давайте перейдем и создадим функцию, которая примет значение FunHistory и значение ввода, и переместите историю. К сожалению, это не полная функция; он не определен для Result типа FunHistory.

-- The caller should make sure it isn't a `Result` type before using this function 
app :: a -> FunHistory a b -> FunHistory a b 
app x (Result _ _)  = undefined 
app x (Application f _ _) = f x 
app x (Base f)   = f x 

Это прекрасно и денди для функций одного аргумента, но промежуточный Application конструктор никогда не требуется для таких простых случаев. Давайте попробуем создать смарт-конструктор для функции 2-аргумента:

mkHist2 :: (a -> a -> b) -> FunHistory a b 
mkHist2 f = let h = Base (\x -> mkHist' f x h) 
      in h 

mkHist' f x h = let h' = Application (\y -> Result (f x y) h') x h 
       in h' 

Давайте попробуем для функции 3-аргумента теперь:

mkHist3 :: (a -> a -> a -> b) -> FunHistory a b 
mkHist3 f = let h = Base (\x -> mkHist2' f x h) 
      in h 

mkHist2' f x h = let h' = Application (\y -> mkHist' (f x) y h') x h 
       in h' 

Теперь 4-аргумент функции:

mkHist4 :: (a -> a -> a -> b) -> FunHistory a b 
mkHist4 f = let h = Base (\x -> mkHist3' f x h) 
      in h 

mkHist3' f x h = let h' = Application (\y -> mkHist2' (f x) y h') x h 
       in h' 

Хорошо посмотрите на это; эти функции выглядят почти точно как mkHist3 и mkHist2' соответственно! Следующим шагом здесь было бы обобщить эти функции на класс, чтобы он масштабировался до функций с произвольным количеством входов. Уловка состоит в том, что все входы должны иметь один и тот же тип.

[предупреждение: этот код не тестировался, но я несколько уверен, что это в основном правильно ... иш]

instance (Show a, Show b) => Show (FunHistory a b) where 
    show (Base _) = "base" 
    show (Application _ x h) = "app " ++ show x ++ ", " ++ show h 
    show (Result r h) = "result: " ++ r ++ ", " ++ show h