Writing insertionSort using foldr and a helper function
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.
Le 29/09/2016 à 20:09, jorgemal1960@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
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.htm... :: (a -> b -> b) -> b -> [a] -> b http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.htm... 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.htm... :: (a -> [a] -> [a]) -> [a] -> [a] -> [a] http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.htm... 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@unicaen.fr> wrote:
Le 29/09/2016 à 20:09, jorgemal1960@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.
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.
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-usi... 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
participants (5)
-
Jake -
Jerzy Karczmarczuk -
jorgemal1960＠gmail.com -
MarLinn -
Richard A. O'Keefe