Haskell - fmap для дерева с переменным количеством узлов в - PullRequest
Новая
       8

Haskell - fmap для дерева с переменным количеством узлов в

0 голосов
/ 31 января 2020

У меня есть определение типа данных: 

data RoseTree a = Leaf a | Branch [RoseTree a] deriving (Eq, Show)

Мне нужно написать fmap Functor 

fmap :: Functor f => (a -> b) -> f a -> f b

Я начал с 

fmap f (Leaf a) =  Leaf (f a)
fmap f (Branch [] ) =  Branch []
fmap f (Branch (x:xs) ) =   ??? -- stuck here

Но теперь я Я застрял и не могу добиться прогресса - надеюсь, кто-то может направить меня. Спасибо!

Ответы [ 2 ]

2 голосов
/ 31 января 2020

Я думаю, что этот код работает 

 instance Functor RoseTree where
  fmap f (Leaf a) =  Leaf (f a)
  fmap f (Branch xs ) =  Branch (map (fmap f) xs)

Я все еще пытаюсь понять, почему.

2 голосов
/ 31 января 2020

Общая структура рекурсивной функции в RoseTree: 

forestFun :: [RoseTree a] -> r
forestFun [] = _
forestFun (xs : xss) = _
    where recXs = treeFun xs
          recXss = forestFun xss

treeFun :: RoseTree a -> r
treeFun (Leaf x) = _
treeFun (Branch xss) = forestFun xss

Причина в том, что это две функции, а не одна, потому что RoseTree - это на самом деле два типа данных, а не один. Обратите внимание, что тип данных RoseTree на самом деле не относится к самому себе, а к спискам деревьев (которые называются «лесами»). Они представляют собой два типа данных, определенных друг с другом, что делает их неразделимыми. 

type Forest a = [RoseTree a]
-- data Forest a = [] | (:) (RoseTree a) (Forest a)
data RoseTree a = Leaf a | Branch (Forest a)

Часто forestFun будет скрыто как предложение where внутри treeFun. Кроме того, поскольку RoseTree на самом деле не упоминает RoseTree (но Forest упоминает обе), вы можете объединить две функции несколько уродливо: 

treeFun :: RoseTree a -> r
treeFun (Leaf x) = _
treeFun (Branch []) = _
treeFun (Branch (x : xs)) = _
     where recXs = treeFun (Branch xs)

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

...