class - 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': 
[] :> []

但是我不确定为什么它不起作用，有人可以帮我吗？

提前致谢!

此致，
斯凯菲。

Answer 1

您对 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