haskell - 如何为这个特定结构实现 foldr？

Question

我正在学习 Haskell。我有一个看起来像这样的列表:

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两个 a TwoValueList 的内部并以某种方式组合它们。我是否缺少其他类型约束？
谢谢你。

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在 TwoValueList 的递归实例上递归调用自身相互嵌入，直到满足 Empty .此时它返回 ini这是初始值，调用堆栈会解决上面的所有函数调用。