如何为这种类型编写 Foldable 实例？

Question

我定义了以下数据类型：

data SynthesisTreeResult comp a = CompNode (comp a) [SynthesisTreeResult comp a]
                                | InputLeaf Location

我希望能够使用 toList 将其转换为类型 [comp a] 的列表，这需要 Foldable.

的实例

我尝试通过实现 foldMap:

来编写一个实例

class Foldable f where
  foldMap :: Monoid m => (a -> m) -> f a -> m

但是，由于 comp :: * -> *，我必须写 instance Foldable (SynthesisTreeResult comp) where ...，这导致 foldMap 具有以下类型

foldMap :: Monoid m => (a -> m) -> SynthesisTreeResult comp a -> m

但我需要

foldMap :: Monoid m => (comp a -> m) -> SynthesisTreeResult comp a -> m

能够折叠。

可能吗？也许我需要在 comp 上施加 Functor?

Answer 1

感谢 @Willem Van Onsem 提示，我找到了正确的实例：

instance Foldable comp => Foldable (SynthesisTreeResult comp) where
  foldMap f (CompNode comp children) = mappend (foldMap f comp) $ mconcat $ map (foldMap f) children

Answer 2

根据您的意见，您想要 comp a 而不是 a，您需要对您的类型进行小的更改：

data SynthesisTreeResult t = CompNode t [SynthesisTreeResult t]
                           | InputLeaf Location

这是必要的，因为从 foldMap 出来的类型总是进入的类型的最后一个类型参数。修复你的类型的用法很容易；只需将 SynthesisTreeResult Foo Bar 更改为 SynthesisTreeResult (Foo Bar) 即可。进行了更改后，这是您的 Foldable 实例：

instance Foldable SynthesisTreeResult where
    foldMap f (CompNode x xs) = f x <> foldMap (foldMap f) xs
    foldMap _ (InputLeaf _) = mempty

如果对您的类型所做的更改不可接受，那么您就不能使用 Foldable 来获得您想要的内容，您需要编写自己的 toList 方法，您可以这样做：

myToList :: SynthesisTreeResult comp a -> [comp a]
myToList (CompNode x xs) = x:concatMap myToList xs
myToList (InputLeaf _) = []

如何为这种类型编写 Foldable 实例？

How do I write Foldable instance for this type?

haskell

typeclass

fold