我如何实现这个特定结构的foldr？

Question

我正在学习哈斯克尔。我有一个如下所示的列表：

data TwoValueList a = Empty | Node a a (TwoValueList a)

我希望这样做Foldable，这样我就可以进行如下计算：

sum (Node 0 1 (Node 2 3 Empty)) --should produce 6

如果只有一个值，那就很容易了：

data OneValueList = Empty | Node a (OneValueList a)
instance Foldable OneValueList where
  foldr f b Empty = b
  foldr f b (Node a rest) = f a (foldr f b rest)

但是，如果一个节点内有两个值，我无法微调类型，因为f需要a和b，但我必须应用于内的f两个值并以某种方式将它们组合起来。我是否缺少其他类型的约束？aTwoValueList

谢谢。

Answer 1

data TwoValueList a = Empty | Node a a (TwoValueList a)

instance Foldable TwoValueList where
  foldr _ ini Empty = ini
  foldr f ini (Node x y xs) = f x $ f y $ foldr f ini xs

其工作方式是在相互嵌入的foldr递归实例上递归地调用自身，直到遇到。此时，它返回初始值，并且调用堆栈出现，解决上面的所有函数调用。TwoValueListEmptyini