Haskell моноид складного розового дерева

Question

мне нужно сделать складной экземпляр для роз древовидной структуры данных:

data Rose a = a :> [Rose a] 
    deriving (Eq, Show) 

Со следующим моноиде и розы связанных классов/экземпляры:

instance Functor Rose where 
    fmap f (a :> bs) = (f a) :> (map (fmap f) bs) 

class Monoid a where 
    mempty ::   a 
    (<>) :: a -> a -> a 

instance Monoid [a] where 
    mempty = [] 
    (<>) = (++) 

Я пробовал:

instance Foldable Rose where 
    fold (a:>b) = a <> (foldMap fold b) 

Однако это не работает должным образом, для проверки системы я получаю ошибку:

*** Failed! Exception: 'Prelude.undefined': 
[] :> [] 

Но я не уверен, почему это не работает, может ли кто-нибудь помочь мне?

Заранее благодарен!

С наилучшими пожеланиями, Skyfe.

Answer 1

Кажется, я нашел ответ на свой вопрос.

Решение:

instance Foldable Rose where 
    fold (a:>b) = a <> (foldr (<>) mempty (map fold b)) 

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

Answer 2

Ваша реализация fold была верна, нет оснований для ее изменения.

Проблема в том, что fold недостаточно для определения Foldable. От the documentation:

class Foldable t where Source

Data structures that can be folded.

Minimal complete definition: foldMap or foldr .

Таким образом, вы должны определить либо foldMap или foldr (или оба). Определение foldMap проще и естественнее (а также более эффективно во многих случаях). Таким образом, вы должны написать что-то вроде:

import Data.Foldable 
import Data.Monoid 

data Rose a = a :> [Rose a] 
    deriving (Eq, Show) 

instance Foldable Rose where 
    foldMap f (x :> xs) = f x <> foldMap (foldMap f) xs 

Answer 3

Это лишь косвенное отношение, но если вы понимаете, что Роза деревья такие же, как Cofree [] от Control.Comonad.Cofree, то вы можете получить Foldable экземпляр «бесплатно» из складного экземпляра из [] так:

import Control.Comonad.Cofree 
import Data.Foldable as F 

type RoseTree = Cofree [] 

Загрузите его в GHCi:

λ> let tree = 1 :< [1 :< [], 2 :< [], 3 :< []] :: RoseTree Int 
λ> :t F.foldr (+) 0 tree 
F.foldr (+) 0 tree :: Int 
λ> F.foldr (+) 0 tree 
7 

Вы также можете дзю st выводить Foldable или написать свою собственную реализацию (как вы это сделали).

Answer 4

Хотя OP говорит, что он/она нашла ответ, решение не имеет базовый случай:

instance Foldable Rose where 
    fold (a:>[]) = a <> mempty 
    fold (a:>b) = a <> (foldr (<>) mempty (map fold b)) 

Иначе expection о неисчерпывающих моделях в функции сгибе будет выброшен.