Implementation of quick sort using haskel

Question

I was wondering why my quick sort code below shows the 'Unresolved top-level overloading error'

sort = \xs -> case xs of
                [] -> []
                y:ys -> sort[p | p <- ys, p < y]
                        ++ y:sort[p| p <- ys, p > y]

Can you let me know why?

Is this all the code in your file? This snippet own it's own gives me a different error — shree.pat18, Jun 11 '21 at 06:50
@WillNess I got the type inference error due to use of < and > on GHCI, but not the one OP did. Agree that might just be Hugs — shree.pat18, Jun 11 '21 at 11:27
@shree.pat18 I deleted my comment since reading the answer, which links to an answer about monomorphism restriction. I might have a flag set in my ghci that prevents the error, or maybe it's version dependent... — Will Ness, Jun 11 '21 at 11:29

score 1 · Accepted Answer · answered Jun 11 '21 at 07:01

1

The type of this function cannot be inferred, because there are multiple types possible with the constraint that < and > are used. You can fix this by adding a signature such as below (as general as possible). Btw your implementation deletes recurring elements. Using <= instead of <fixes this:

sort :: Ord a => [a] -> [a]
sort = \xs -> case xs of
                [] -> []
                y:ys -> sort[p | p <- ys, p <= y]
                        ++ y:sort[p| p <- ys, p > y]

Example call (double 7's):

> sort [12,34,2,4,7,6,34,7,3]
[2,3,4,6,7,7,12,34,34]

answered Jun 11 '21 at 07:01

jf_

3,099
2
13
31

Thank you for your answering. I changed my code not using lambda then it worked without adding 'sort :: Ord a => [a] -> [a]'. Can you let me know why? – blueMountain Jun 11 '21 at 07:14
This is because the binding and type inference is handled differently. See [this answer](https://stackoverflow.com/a/37169791/14627587) and [this very long answer](https://stackoverflow.com/a/32496865/14627587). – jf_ Jun 11 '21 at 07:30

Implementation of quick sort using haskel

1 Answers1