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

[Richard A. O'Keefe]

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.