Three examples of recursion schemes drawn from mathematics, showing the use of linked lists as control structures.

# Paramorphisms

## Integer Partitions

import Numeric.Natural       (Natural)
import Control.Monad         (join)
import Data.List             (nub)
import Data.Functor.Foldable (ListF (..), para)partitions :: Natural -> [[Natural]]
partitions = para algebra
where algebra Nothing          = []
algebra (Just (0,_))     = []
algebra (Just (_, past)) = (nub . (getAll =<<)) (fmap (1:) past)getAll :: [Natural] -> [[Natural]]
getAll = fmap (dropWhile (==0) . sort) . subsets
where subsets xs = flip sumIndicesAt xs <$> indices xsindices :: [Natural] -> [[Natural]] indices = join . para algebra where algebra Nil = [] algebra (Cons x (xs, [])) = [[x:xs]] algebra (Cons x (xs, past)) = (:) <$> [x:xs,[]] <*> pastsumIndicesAt :: [Natural] -> [Natural] -> [Natural]
sumIndicesAt ix = (\(a, b) -> sum a : b) . partition (elem ix)

# Apomorphisms

## Continued Fractions

import           Data.Functor.FoldableisInteger :: (RealFrac a) => a -> Bool
isInteger = idem (realToFrac . floor)
where idem = ((==) <*>)continuedFraction :: (RealFrac a, Integral b) => a -> [b]
continuedFraction = apo coalgebra
where coalgebra x
| isInteger x = go $Left [] | otherwise = go$ Right alpha
where alpha = 1 / (x - realToFrac (floor x))
go    = Cons (floor x)

## Base Conversions

import Data.Functor.FoldableintegerToWordList :: Integral a => a -> a -> [a]
integerToWordList base = apo pc where
pc i | i < base = Cons (fromIntegral i) (Left mempty)
| otherwise = Cons (fromIntegral (i mod base)) (Right (i div base))

# Elgot Algebras

## Lengths of Collatz Sequences

import Data.Functor.FoldablecollatzLength :: Int -> Int
collatzLength = elgot algebra coalgebracoalgebra :: Int -> Either Int (ListF Int Int)
coalgebra 1 = Left 1
coalgebra n
| n mod 2 == 0 = Right $Cons n (div n 2) | otherwise = Right$ Cons n (3 * n + 1)algebra :: ListF Int Int -> Int
algebra Nil        = 0
algebra (Cons _ x) = x + 1

# Co-(Elgot Algebra)s

## Base Conversions

import Data.Functor.FoldableintegerToBase :: (Integral a) => a -> a -> [a]
integerToBase base = coelgot pa c where
c i = Cons (i mod base) (i div base)
pa (i, ws) | i < base = [fromIntegral i]
| otherwise = embed ws

# Mendler-Style Catamorphisms

## Base Conversions

import Data.Functor.FoldablewordListToInteger :: (Integral a) => a -> [a] -> a
wordListToInteger base = mcata ma . cata Fix where
ma f (Cons x xs) = fromIntegral x + base * f xs
ma _ Nil         = 0