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.