Функция карты Haskell для алгебраических типов данных

У меня есть алгебраический тип данных Newb, определенный, как показано ниже. Теперь я хочу написать для него собственную функцию карты без использования рекурсии. Кроме того, у меня есть функция foldNewb, которая также может помочь.

 data Newb a = Leaf a | Node [Newb a]


foldNewb:: (a->b)->([b]->b)->Newb a -> b
foldNewb f _ (Leaf a) = f a
foldNewb f1 f2 (Node a) = f2 (map (foldNewb f1 f2) a)


Newbmap :: (a->b)-> Newb a -> Newb b

Newbmap f (Leaf a) = (Leaf (f a))
Newbmap f (Node a) = (Node (foldNewb f concat a))

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


functional-programming higher-order-functions fold haskell algebraic-data-types
person Highness    schedule 02.08.2018    source источник

Ответы (2)


arrow_upward
5
arrow_downward

tl;dr Вот ваша функция. Но я рекомендую читать дальше, чтобы увидеть, как я пришел к этому, чтобы вы могли разобраться в мыслительном процессе.

newbmap :: (a->b)-> Newb a -> Newb b
newbmap f = foldNewb (Leaf . f) Node

Вы довольно близки, и вы правильно используете foldNewb, но вы слишком много обдумываете.

Во-первых, вы не можете назвать функцию Newbmap. Заглавные имена зарезервированы для типов. Итак, мы назовем его newbmap. Теперь foldNewb уже обрабатывает оба случая Leaf и Node, поэтому нам вообще не нужно сопоставлять шаблоны в newbmap. Фактически, ваш первый случай newbmap делает именно то, что в любом случае сделал бы foldNewb, так что давайте просто рассмотрим второй случай.

newbmap :: (a->b)-> Newb a -> Newb b
newbmap f (Node a) = (Node (foldNewb f concat a))

Мы хотим свернуть нашу структуру данных. В частности, мы хотим, чтобы наш вызов fold полностью создавал новую структуру данных. Нам не следует явно использовать Node в конце, так как, опять же, foldNewb уже работает за нас.

newbmap :: (a->b)-> Newb a -> Newb b
newbmap f a = foldNewb f concat a

Теперь в первом случае нам нужна функция a -> Newb b (поскольку результат будет иметь тип Newb b). Вы прошли f :: a -> b, что очень близко к тому, что вы хотите. Нам просто нужно составить его с помощью функции b -> Newb b, а Leaf сделает именно это.

newbmap :: (a->b)-> Newb a -> Newb b
newbmap f a = foldNewb (Leaf . f) concat a

В качестве второго аргумента вам нужно [Newb b] -> Newb b, что опять же очень легко сделать с помощью Node.

newbmap :: (a->b)-> Newb a -> Newb b
newbmap f a = foldNewb (Leaf . f) Node a

И (хотя это не имеет значения) мы можем без указания последнего аргумента.

newbmap :: (a->b)-> Newb a -> Newb b
newbmap f = foldNewb (Leaf . f) Node

Итак, есть работающая функция newbmap. Теперь, что касается того, как я пришел ко всем этим типам, если вы используете GHC, есть очень полезная функция под названием отверстия для типов, которую вы можете использовать, чтобы определить, какие типы вам нужны. Итак (и я сделал именно это при отладке вашей функции), если вы пишете

newbmap :: (a->b)-> Newb a -> Newb b
newbmap f = foldNewb _1 _2

тогда вы получите очень конкретные сообщения GHC, сообщающие вам _1 :: a -> Newb b и _2 :: [Newb b] -> Newb b. Тогда ваша задача состоит в том, чтобы просто найти функции с этими конкретными типами. И здесь я придумал Leaf . f и Node.

person Silvio Mayolo    schedule 02.08.2018

arrow_upward
1
arrow_downward

Без использования foldNewb:

data Newb a = Leaf a | Node [ Newb a]
  deriving (Show)

newbMap :: (a -> b) -> Newb a -> Newb b
newbMap f (Leaf a) = Leaf (f a)
-- since a :: [Newb a] in the below clause, we can map (newbMap f) over the elements 
newbMap f (Node a) = Node (map (newbMap f) a)

tree = Node [ Leaf 1, Node [Leaf 2, Leaf 3], Leaf 4]
mapped = newbMap (+1) tree -- Node [Leaf 2,Node [Leaf 3,Leaf 4],Leaf 5]
person Michiel Borkent    schedule 02.08.2018