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,_)) = [[1]]
algebra (Just (_, past)) = (nub . (getAll =<<)) (fmap (1:) past)

getAll :: [Natural] -> [[Natural]]
getAll = fmap (dropWhile (==0) . sort) . subsets
where subsets xs = flip sumIndicesAt xs <$> indices xs

indices :: [Natural] -> [[Natural]]
indices = join . para algebra
where algebra Nil = []
algebra (Cons x (xs, [])) = [[x:xs]]
algebra (Cons x (xs, past)) = (:) <$> [x:xs,[]] <*> past

sumIndicesAt :: [Natural] -> [Natural] -> [Natural]
sumIndicesAt ix = ((a, b) -> sum a : b) . partition (`elem`

ix)

# Apomorphisms

### Continued Fractions

import Data.Functor.Foldable
import Data.Ratio (Ratio, denominator, (%))

isInteger :: (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)

# Elgot Algebras

### Lengths of Collatz Sequences

import Data.Functor.Foldable

collatzLength :: Int -> Int
collatzLength = elgot algebra coalgebra

coalgebra :: 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