Haskell中如何为自定义双值节点列表结构实现foldr

你不需要额外添加任何类型约束，只需要按顺序对节点内的两个值依次应用折叠函数即可，正确的Foldable实例实现如下：

instance Foldable TwoValueList where
  foldr f b Empty = b
  foldr f b (Node x y rest) = f x (f y (foldr f b rest))

逻辑说明 #

foldr的折叠逻辑是从右向左累计：

1. 先递归处理剩余的子列表rest，得到类型为b的累计值
2. 将节点的第二个值y作为第一个参数传入f，和上述累计值运算得到新的b类型值
3. 再将节点的第一个值x作为第一个参数传入f，和上一步的结果运算，最终得到当前节点的折叠结果

你也可以选择实现更简洁的foldMap方法，Foldable类型类会自动生成foldr的默认实现：

instance Foldable TwoValueList where
  foldMap f Empty = mempty
  foldMap f (Node x y rest) = f x <> f y <> foldMap f rest

两种实现都可以满足你的测试需求：执行sum (Node 0 1 (Node 2 3 Empty))会得到预期结果6。

内容的提问来源于stack exchange，提问作者daikonradish