[Haskell-cafe] Writing insertionSort using foldr and a helper function

Richard A. O'Keefe ok at cs.otago.ac.nz
Fri Sep 30 02:44:06 UTC 2016

```Just to add to what Jerzy Karczmarczuk wrote:

myInsert :: Ord a => a -> [a] -> [a]

I find it clearer to think in terms of "should I keep going"
(rule 1) "or should I stop and insert now" (rule 2).

myInsert x (y : ys) | x>= y = y : myInsert x ys -- continue
myInsert x ys               = x : ys            -- insert now

insertionSort :: Ord a => [a] -> [a]

insertionSort xs = {- some combination of foldr and insert
and xs and something else -}

The types really only allow the pieces to be put together
one way.  Your assignment was almost certainly to use
foldr *INSTEAD* of writing a recursive function, leaving
foldr to worry about managing the recursion.

Let's think about the data type.

data [t]           -- a list of t
= []            -- is an empty list
| (:) t [t]     -- or a non-empty list with a first
-- element that's a t and remaining
-- elements forming a smaller list of t

This leads to a general recursion pattern

f [] = what to do for nil
f (x : xs) = what to do for x and (f xs)

or

foldr :: (t -> r -> r) -> r           -> [t] -> r
-- cons_handler     nil_handler    list   result

foldr c n [] = n
foldr c n (x:xs) = c x (foldr c n xs)

If you have an instance of that general pattern I
mentioned, you can turn it into

f = foldr (what to do for x and fxs) (what to do for nil)

insertionSort [] = []
insertionSort (x:xs) = insert x (insectionSort xs)

is an instance of that general recursion pattern.
```