[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.
More information about the Haskell-Cafe
mailing list