fold package:recursion-schemes

Folds a recursive type down to a value, one layer at a time.

>>> :{
let mySum :: [Int] -> Int
mySum = fold $ \case
Nil -> 0
Cons x sumXs -> x + sumXs
:}

>>> mySum [10,11,12]
33

In our running example, one layer consists of an Int and a list of recursive positions. In Tree Int, those recursive positions contain sub-trees of type Tree Int. Since we are working one layer at a time, the Base t a -> a function is not given a Tree Int, but a TreeF Int String. That is, each recursive position contains the String resulting from recursively folding the corresponding sub-tree.

>>> :{
let pprint1 :: Tree Int -> String
pprint1 = fold $ \case
NodeF i [] -> show i
NodeF i ss -> show i ++ ": [" ++ intercalate ", " ss ++ "]"
:}

>>> putStrLn $ pprint1 myTree
0: [1, 2, 3: [31: [311: [3111, 3112]]]]

More generally, the t argument is the recursive value, the a is the final result, and the Base t a -> a function explains how to reduce a single layer full of recursive results down to a result.

A generalized catamorphism

A generalized hylomorphism

A generalized anamorphism

An optimized version of fold f . unfold g. Useful when your recursion structure is shaped like a particular recursive datatype, but you're neither consuming nor producing that recursive datatype. For example, the recursion structure of quick sort is a binary tree, but its input and output is a list, not a binary tree.

>>> data BinTreeF a b = Tip | Branch b a b deriving (Functor)

>>> :{

>>> let quicksort :: Ord a => [a] -> [a]

>>> quicksort = refold merge split where

>>> split []     = Tip

>>> split (x:xs) = let (l, r) = partition (<x) xs in Branch l x r

>>> 

>>> merge Tip            = []

>>> merge (Branch l x r) = l ++ [x] ++ r

>>> :}

>>> quicksort [1,5,2,8,4,9,8]
[1,2,4,5,8,8,9]

A generalization of unfoldr. The starting seed is expanded into a base functor whose recursive positions contain more seeds, which are themselves expanded, and so on.

>>> :{

>>> let ourEnumFromTo :: Int -> Int -> [Int]

>>> ourEnumFromTo lo hi = ana go lo where

>>> go i = if i > hi then Nil else Cons i (i + 1)

>>> :}

>>> ourEnumFromTo 1 4
[1,2,3,4]