<div dir="ltr">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:<div><br></div><div><a class="inbox-inbox-a" href="http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:foldr" style="color:rgb(196,69,29);text-decoration:none;font-size:16px"><b>foldr</b></a><a class="inbox-inbox-dull" href="http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:foldr" style="color:black;text-decoration:none;font-size:16px"><span class="inbox-inbox-Apple-converted-space"> </span>:: (a -> b -> b) -> b -> [a] -> b</a></div><div><br></div><div>foldr takes:</div><div> - an function that combines the next value (a) and our accumulated value (b) to produce a new accumulated value (b)</div><div> - an initial value for our accumulator (b)</div><div> - a list of as to vold ([a])</div><div><br></div><div>In this case, our accumulated value is the new list, so the type signature can be rewritten like this:</div><div><br></div><div><a class="inbox-inbox-inbox-inbox-a" href="http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:foldr" style="color:rgb(196,69,29);text-decoration:none;font-size:16px"><b>foldr</b></a><a class="inbox-inbox-inbox-inbox-dull" href="http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:foldr" style="color:black;text-decoration:none;font-size:16px"><span class="inbox-inbox-inbox-inbox-Apple-converted-space"> </span>:: (a -> [a] -> [a]) -> [a] -> [a] -> [a]</a><br></div><div><br></div><div>Now we can see we need</div><div> - a function that takes a new element and correctly inserts it into the list in order</div><div> - an initial value for our output list</div><div> - a list to sort</div><div><br></div><div>From this it should be a lot clearer what to pass to foldr.</div></div><br><div class="gmail_quote"><div dir="ltr">On Thu, Sep 29, 2016 at 3:58 PM Jerzy Karczmarczuk <<a href="mailto:jerzy.karczmarczuk@unicaen.fr">jerzy.karczmarczuk@unicaen.fr</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div bgcolor="#FFFFFF" text="#000000">
<div>Le 29/09/2016 à 20:09,
<a href="mailto:jorgemal1960@gmail.com" target="_blank">jorgemal1960@gmail.com</a> a écrit :<br>
</div>
<blockquote type="cite">
<div dir="ltr">
<div>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.<br>
<div>
<div><br>
</div>
</div>
</div>
</div>
</blockquote></div><div bgcolor="#FFFFFF" text="#000000">
** This is most probably some pedagogic assignment, and you should
not expect from the community to solve your exercices. <br>
I suspect that you tried to solve the problem without trying to
UNDERSTAND foldr...<br>
But let's see...<br>
<blockquote type="cite">
<div dir="ltr"></div></blockquote></div><div bgcolor="#FFFFFF" text="#000000"><blockquote type="cite"><div dir="ltr">
<div>
<div>
<div>
<div style="border-width:1px;border-style:solid;border-color:rgb(187,187,187);background-color:rgb(250,250,250);word-wrap:break-word"><code>
<div>myInsert :: Ord a => a -> [a] -> [a]</div>
<div>myInsert x [] = [x]</div>
<div>myInsert x (y:ys) = if x < y then x:y:ys else
y:myInsert x ys</div>
</code></div>
<br>
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:</div>
</div>
</div></div></blockquote></div><div bgcolor="#FFFFFF" text="#000000"><blockquote type="cite"><div dir="ltr">
...<br>
</div>
</blockquote>
OK.</div><div bgcolor="#FFFFFF" text="#000000"><br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div>I have worked for 2 days to use foldr without success, for
example:<br>
</div>
<div><br>
</div>
<div>
<div style="border-width:1px;border-style:solid;border-color:rgb(187,187,187);background-color:rgb(250,250,250);word-wrap:break-word"><code>
<div>insertionSort :: Ord a => [a] -> [a]</div>
<div>insertionSort [] = []</div>
<div>insertionSort [x] = [x]</div>
<div><span style="font-family:Arial,Helvetica,sans-serif">insertionSort (x:xs) = foldr (myInsert) x
(insertionSort xs)</span></div>
</code></div>
<div><br>
</div>
But it does not even compile, I get the following error which
refers to last instruction at position "x" in "<span style="background-color:rgb(250,250,250)">foldr
(myInsert) x (insertionSort xs)":</span></div>
<div><br>
</div>
<div><span style="background-color:rgb(255,255,0)">Couldn't
match expected type ‘[a]’ with actual type ‘a’</span></div>
</div>
</blockquote>
<br></div><div bgcolor="#FFFFFF" text="#000000">
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 <a href="https://wiki.haskell.org/Fold" target="_blank">https://wiki.haskell.org/Fold</a>, or
in the Standard Prelude, say:
<a href="https://www.haskell.org/onlinereport/standard-prelude.html" target="_blank">https://www.haskell.org/onlinereport/standard-prelude.html</a> (e.g.,
the definition of concat). <br>
<br>
B. So, no need for pattern split x:xs in your main definition,
define just<br>
insertionSort xs = ...<br>
<br>
C. Mind the type of foldr, : (a -> c -> c) -> c -> [a]
-> c . <br>
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.<br>
The third element of foldr is the processed container (also list),
just it, no recursion. And your first two clauses of insertionSort
are useless.</div><div bgcolor="#FFFFFF" text="#000000"><br>
<br>
Jerzy Karczmarczuk<br>
</div>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div>