Writing insertionSort using foldr and a helper function

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Writing insertionSort using foldr and a helper function

JORGE MALDONADO
I am posting the same question again because I had not subscribed to the list and I received a message saying it was automatically rejected.

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.
So, if the list is sorted, then the list will remain sorted.

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:

insertionSort :: Ord a => [a] -> [a]
insertionSort [] = []
insertionSort [x] = [x]
insertionSort (x:xs) = myInsert x (insertionSort xs)

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’

I will very much appreciate your feedback in order to solve my issue.

Best regards.

_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Writing insertionSort using foldr and a helper function

Jerzy Karczmarczuk
Le 29/09/2016 à 20:09, [hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: 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 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:


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 <[hidden email]> wrote:
Le 29/09/2016 à 20:09, [hidden email] 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.

_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Writing insertionSort using foldr and a helper function

Haskell - Haskell-Cafe mailing list
In reply to this post by JORGE MALDONADO
I can not add more from a teaching standpoint because I can not see what
the underlying real problem is. But it seems there's a
stack-overflow-question that is connected.

http://stackoverflow.com/questions/39710307/how-do-i-write-insertionsort-using-foldr

Please consider including links to existing discussions of a problem in
the future. If that question is indeed connected, the down-votes seem to
imply you should change your approach. That apparently hasn't happened
in the last two days, so I advise trying that. Even if it doesn't help
directly, it might bring up new questions that mentors can use as a
pivot. Good luck.


Cheers,
MarLinn
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Writing insertionSort using foldr and a helper function

Richard A. O'Keefe
In reply to this post by Jerzy Karczmarczuk
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.
_______________________________________________
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.