Is it possible to automatically define this function for any arbitrary data type?

Question

Mind the definition of the fold function below:

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

This function as a very regular way to be defined, but it depends on the maximum number of recursive branches a data constructor of that type has. That is, T has a constructor with 2 recursion points C T T, so "fold" receives three "up" arguments. If C T T was not part of the type, then the definition of fold would take one less argument:

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

My question is wether it is possible to create a definition of fold automatically using deriving.

Answer 1

Defining this via deriving alone can be a bit of a pain. But if you know the algorithm, then the Generics package can let you write it, and you can then use default signatures to "autoderive" an instance with slightly different but still nice syntax.

Two libraries that might serve you well in this regard are: https://hackage.haskell.org/package/generic-deriving and https://hackage.haskell.org/package/generics-sop