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

[Jerzy Karczmarczuk]

Le 29/09/2016 à 20:09, jorgemal1960 at gmail.com a écrit :
> I have the following function that takes an element and a list and 
> inserts the element into the list at the first position where it is 
> less than or equal to the next element.
>
** This is most probably  some pedagogic assignment, and you should not 
expect from the community to solve your exercices.
I suspect that you tried to solve the problem without trying to 
UNDERSTAND foldr...
But let's see...
> |
> myInsert :: Ord a => a -> [a] -> [a]
> myInsert x [] = [x]
> myInsert x (y:ys) = if x < y then x:y:ys else y:myInsert x ys
> |
>
> Now, I have to use the above function myInsert and foldr to implement 
> another function called insertionSort. I have been able to do it 
> without using foldr as follows and it works just fine:
> ...
OK.

> I have worked for 2 days to use foldr without success, for example:
>
> |
> insertionSort :: Ord a => [a] -> [a]
> insertionSort [] = []
> insertionSort [x] = [x]
> insertionSort (x:xs) = foldr (myInsert) x (insertionSort xs)
> |
>
> But it does not even compile, I get the following error which refers 
> to last instruction at position "x" in "foldr (myInsert) x 
> (insertionSort xs)":
>
> Couldn't match expected type ‘[a]’ with actual type ‘a’

A. You should have learnt that the usage of generic functionals such as 
foldr is to avoid explicit recursion. Please, look up some examples of 
foldr, for example in https://wiki.haskell.org/Fold, or in the Standard 
Prelude, say: 
https://www.haskell.org/onlinereport/standard-prelude.html  (e.g., the 
definition of concat).

B. So, no need for pattern split x:xs in your main definition, define just
insertionSort xs = ...

C. Mind the type of foldr, : (a -> c -> c) -> c -> [a] -> c .
The type of your function is ok (parentheses redundant), but the second 
argument is the initial container (list) while you have chosen "x", 
which is an element. Here the typechecker protests, but this is not your 
only mistake.
The third element of foldr is the processed container (also list), just 
it, no recursion. And your first two clauses of insertionSort are useless.

Jerzy Karczmarczuk
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20160929/5fdd1049/attachment.html>