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