Lex Augusteijn points out in "Sorting morphisms" that some sorting
algorithms are determined entirely by their recursion pattern.
(We can abstract the algorithm from the structure to be sorted,
if we know how to traverse that structure.)
# 3.2 Origami with lists: sorting
Some familiar definitions:
data List α = Nil | Cons α (List α)
wrap ∷ α → List α
wrap x = Cons x Nil
nil ∷ List α → Bool
nil Nil = True
nil (Cons _ _) = False
This is actually the right fold; ‘L’ here is for ‘list’:
foldL ∷ (α → β → β) → β → (List α) → β
foldL f e Nil = e
foldL f e (Cons x xs) = f x (foldL f e xs)
The universal property of foldL:
If h ∷ (List α) → β is some function, then
h = foldL f e
if and only if
h xs = case xs of
Nil → e
Cons y ys → f y (h ys)
Insertion sort with explicit recursion:
isort ∷ Ord α ⇒ List α → List α
isort = foldL insert Nil
where
insert ∷ Ord α ⇒ α → List α → List α
insert y Nil = wrap y
insert y (Cons x xs)
| y < x = Cons y (Cons x xs)
| otherwise = Cons x (insert y xs)
# Unfolds for lists
Unfolding is dual to folding. The two common versions of list unfold:
-- Maybe-based version, familiar to Data.List users.
unfoldL′ ∷ (β → Maybe (α, β)) → β → List α
unfoldL′ f u = case f u of
Nothing → Nil
Just (x, v) → Cons x (unfoldL′ f v)
-- Predicate-based version.
unfoldL ∷ (β → Bool) → (β → α) → (β → β) → β → List α
unfoldL p f g b = if p b
then Nil
else Cons (f b) (unfoldL p f g (g b))
(Note: wrap as an unfold is pretty trivial, but we can’t write it
directly because we’d need a value of the same type as x that is not x
to stop the unfold. We have to do an interesting little dance:
wrap x = unfoldL isNothing fromJust (const Nothing) (Just x)
)
We have a universal property for unfoldL:
h = unfoldL p f g
iff
h b = if p b then Nil else Cons (f b) (h (g b))
We also have a single-argument version of foldL, analogous to
unfoldL′:
foldL′ ∷ (Maybe (α, β) → β) → List α → β
foldL′ f Nil = f Nothing
foldL′ f (Cons x xs) = f (Just (x, foldL′ f xs))
Selection sort: We unfold a sorted list from an input list by
successively taking the minimum element of the input list without
disordering the remaining sublist.
ssort ∷ Ord α ⇒ List α → List α
ssort = unfoldL′ delmin
delmin ∷ Ord α ⇒ List α → Maybe (α, List α)
delmin Nil = Nothing
delmin xs = Just (y, deleteL y xs)
where y = minimumL xs
minimumL (Cons x xs) = foldL min x xs
deleteL ∷ Eq α ⇒ α → List α → List α
deleteL y Nil = Nil
deleteL y (Cons x xs)
| y == x = xs
| otherwise = Cons x (deleteL y xs)
The infamous bubble sort is also an unfold.
bsort ∷ Ord α ⇒ List α → List α
bsort = unfoldL' bubble
bubble ∷ Ord α ⇒ List α → Maybe (α, List α)
bubble = foldL step Nothing
where
step x Nothing = Just (x, Nil)
step x (Just (y, ys))
| x < y = Just (x, Cons y ys)
| otherwise = Just (y, Cons x ys)
‘bubble’ doesn’t maintain the relative order of the remaining list
elements, so it's possible to define it as a fold.
## Hylomorphisms
Hylomorphism = unfold followed by fold.
hyloL f e p g h = foldL f e ∘ unfoldL p g h
For example,
fact = hyloL (×) 1 (== 0) id pred
Hylomorphism fusion (deforestation) eliminates the intermediate
structure:
hyloL f e p g h b = if p b
then e
else f (g b) (hyloL f e p g h (h b))
Fold-then-unfold (called a *metamorphism* by Gibbons) is more obscure,
and is a useful pattern for translation between data formats.