Dear Jose,
> I am trying to define common functions with recursive combinators
> avoiding recursive definitions. I have found some problems with
> the "insert" function that inserts an element x in an ordered list xs
> This function is used when you define insertion sort as "foldr insert []"
>
> -- First attempt
> insert::(Ord a)=>a->[a]->[a]
> insert x = foldr (\x (y:ys) -> if x < y then x:y:ys
> else y:x:ys) [x]
That looks like bubbling an element down (ie `foldr insert []' yields
bubble sort rather than insertion sort).
BTW I like to think of `foldr' as a special case of _structural
recursion on lists_.
> structuralRecursionOnLists
> :: solution -- base
> -> (a -> [a] -> solution -> solution) -- extend
> -> [a] -> solution
> structuralRecursionOnLists base extend
> = rec
> where rec [] = base
> rec (a : x) = extend a x (rec x)
>
> insertionSort :: (Ord a) => [a] -> [a]
> insertionSort = structuralRecursionOnLists
> []
> (\a _ s -> insert a s)
>
> insert :: (Ord a) => a -> [a] -> [a]
> insert a = structuralRecursionOnLists
> [a]
> (\b x s -> if a <= b then a : b : x else b : s)
Regard, Ralf
