Haskell monoid可折叠玫瑰树

Question

我需要为Rose树数据结构创建一个可折叠的实例:

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

使用以下monoid和rose相关的类/实例:

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

你的实施fold是正确的,没有理由改变它.

问题是fold不足以定义Foldable.从文档:

class Foldable t where Source

可以折叠的数据结构.

最小的完整定义:foldMap或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 2

这只是切线相关,但如果您意识到Rose Trees与Cofree []from 相同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

您也可以只是派生Foldable或编写自己的实现(就像您已经完成的那样).

Answer 3

似乎我找到了自己问题的答案。

解决方案：

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

必须首先将列表中的每个元素附加到头元素（并对每个绑定到这些玫瑰树的元素执行相同的操作），然后将列表与非调整元素 mempty 折叠在一起。