Insertion sort as a fold
I've written several posts lately about various algorithms that can be expressed as functional folds:
These have all been numerical algorithms. Insertion sort is an example of a non-numerical algorithm that could be implemented as a fold.
Insertion sort is not the fastest sorting algorithm. It takes O(n2) operations to sort a list of size n while the fastest algorithms take O(n log n) operations. But insertion sort is simple, and as it works its way down a list, the portion it has processed is sorted. If you interrupt it, you have correct results given the input so far. If you interrupt something like a quicksort, you don't have a sorted list. If you're receiving a stream of data points and want to sort them as they come, you have to use insertion sort rather than something like quicksort.
The function to fold over a list looks like this:
f as a = [x | x <- as, x < a] ++ [a] ++ [x | x <- as, x >= a]
Given a sorted list as and a value a, return a new sorted list that has inserted the element a in the proper position. Our function f does this by joining together the list of the elements less than a, the list containing only a, and the list of elements at least as big as a.
Here's how we could use this to alphabetize the letters in the word "example."
foldl f [] "example"
This returns "aeelmpx".
Haskell takes our function f and an empty list of characters [] and returns a new list of characters by folding f over the list of characters making up the string "example".
You can always watch how foldl works by replacing it with scanl to see intermediate results.
scanl f [] "example"
returns
["", "e", "ex", "aex", "aemx", "aempx", "aelmpx", "aeelmpx"]