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

[Jake]

>From an intuitive perspective, I think the first step is to look at the
type of foldr and identify what the individual parts of that type mean:

*foldr*
<http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:foldr>
 :: (a -> b -> b) -> b -> [a] -> b
<http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:foldr>

foldr takes:
  - an function that combines the next value (a) and our accumulated value
(b) to produce a new accumulated value (b)
  - an initial value for our accumulator (b)
  - a list of as to vold ([a])

In this case, our accumulated value is the new list, so the type signature
can be rewritten like this:

*foldr*
<http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:foldr>
 :: (a -> [a] -> [a]) -> [a] -> [a] -> [a]
<http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:foldr>

Now we can see we need
  - a function that takes a new element and correctly inserts it into the
list in order
  - an initial value for our output list
  - a list to sort

>From this it should be a lot clearer what to pass to foldr.

On Thu, Sep 29, 2016 at 3:58 PM Jerzy Karczmarczuk <
jerzy.karczmarczuk at unicaen.fr> wrote:

> 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
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20160929/7e5420c6/attachment.html>