Haskell's base library contains several functions which are the lowercase versions of their respective data types, like bool
, maybe
and either
. In the source code of Data.Bool.Extra, the bool
function is clearly expressed as the data type's catamorphism:
bool = curry cata
Now, using the catamorphism as defined in Recursion Schemes by Example, it seems like the above-mentioned base library functions are all the catamorphisms of their data type, e.g. for Maybe:
-- base library definition
maybe n _ Nothing = n
maybe _ f (Just x) = f x
-- definition with cata
newtype Fix f = Fix {unFix :: f (Fix f)}
cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg = alg . fmap (cata alg) . unFix
maybe n f m = cata alg where
alg Nothing = n
alg (Just x) = f x
However, Data.List.Extra's list
function is just mentioned in the comments as a "Non-recursive transform over a list, like 'maybe'", but as it is non-recursive in contrast to its data type, it apparently is not any recursion scheme of list either, or is it? Is that why it's not defined in the base library? Does the function have any other nice theoretical properties?
The catamorphism for []
is foldr
.
The list
function from the extra
package is a conversion to Scott encoding, in the way that a catamorphism is a conversion to Church encoding. Since Scott encodings are non-recursive, they can't really correspond to any recursion scheme.