7

我需要为玫瑰树数据结构制作一个可折叠的实例：

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。

4

4 回答 4

8

你的实现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
于 2014-10-08T18:31:56.030 回答
5

这只是切线相关，但如果您意识到 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或编写自己的实现（就像您所做的那样）。

于 2014-10-08T20:42:26.570 回答
3

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

解决方案：

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

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

于 2014-10-08T15:31:06.243 回答
0

尽管 OP 说他/她找到了答案，但解决方案缺乏基本情况：

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

否则，将引发对函数 fold 中非详尽模式的期望。

于 2015-12-11T15:05:31.010 回答