haskell - 是否可以为任意数据类型自动定义此函数？

Question

注意下面fold函数的定义:

data T = A | B T | C T T
fold up2 up1 up0 down accum x   = dig x accum where
    dig (C a b) accum           = up2 C a b accum (dig a (down (C a b) accum)) (dig b (down (C a b) accum)) 
    dig (B a) accum             = up1 B a accum (dig a (down (B a) accum))
    dig A accum                 = up0 A accum

这个函数作为一个非常规则的方式被定义，但是它取决于该类型的数据构造函数具有的最大递归分支数。也就是说，T 有一个带有 2 个递归点的构造函数 C T T，因此“fold”接收三个“up”参数。如果 C T T 不是类型的一部分，那么 fold 的定义将少一个参数:

data T = A | B T
fold up1 up0 down accum x = dig x accum where
    dig (B a) accum = up1 B a accum (dig a (down (B a) accum))
    dig A accum     = up0 A accum

我的问题是是否可以使用 deriving 自动创建 fold 的定义。

Answer 1

单独通过 deriving 定义它可能会有点痛苦。但是如果您知道该算法，那么 Generics 包可以让您编写它，然后您可以使用默认签名来“自动派生”一个具有略微不同但仍然很好的语法的实例。

在这方面可能对您有帮助的两个库是:https://hackage.haskell.org/package/generic-deriving和 https://hackage.haskell.org/package/generics-sop