3

Quick sort:

-- First variant: qsort :: (Ord a) => [a] -> [a] qsort [] = [] qsort (x:xs) = left x ++ [x] ++ right x where left n = qsort [m | m <- xs, m <= n] right n = qsort [m | m <- xs, m > n] -- λ: qsort [10,2,5,3,1,6,7,4,2,3,4,8,9] -- [1,2,2,3,3,4,4,5,6,7,8,9,10]

I see the left and right functions are almost identical. Therefore I want to rewrite it shorter... Something like that:

-- Second variant: qsort' :: (Ord a) => [a] -> [a] qsort' [] = [] qsort' (x:xs) = (srt <=) ++ [x] ++ (srt >) where srt f = qsort' [m | m <- xs, m f x]

But I get errors when I try to load this into ghci:

λ: :load temp [1 of 1] Compiling Main ( temp.hs, interpreted ) temp.hs:34:18: Couldn't match expected type `[a]' with actual type `(t0 -> [a]) -> Bool' Relevant bindings include srt :: forall t. t -> [a] (bound at temp.hs:35:9) xs :: [a] (bound at temp.hs:34:11) x :: a (bound at temp.hs:34:9) qsort' :: [a] -> [a] (bound at temp.hs:33:1) In the first argument of `(++)', namely `(srt <=)' In the expression: (srt <=) ++ [x] ++ (srt >) In an equation for qsort': qsort' (x : xs) = (srt <=) ++ [x] ++ (srt >) where srt f = qsort' [m | m <- xs, m f x] temp.hs:34:37: Couldn't match expected type `[a]' with actual type `(t1 -> [a]) -> Bool' Relevant bindings include srt :: forall t. t -> [a] (bound at temp.hs:35:9) xs :: [a] (bound at temp.hs:34:11) x :: a (bound at temp.hs:34:9) qsort' :: [a] -> [a] (bound at temp.hs:33:1) In the second argument of `(++)', namely `(srt >)' In the second argument of `(++)', namely `[x] ++ (srt >)' In the expression: (srt <=) ++ [x] ++ (srt >) temp.hs:35:38: Could not deduce (a ~ (t -> a -> Bool)) from the context (Ord a) bound by the type signature for qsort' :: Ord a => [a] -> [a] at temp.hs:32:11-31 `a' is a rigid type variable bound by the type signature for qsort' :: Ord a => [a] -> [a] at temp.hs:32:11 Relevant bindings include m :: a (bound at temp.hs:35:29) f :: t (bound at temp.hs:35:13) srt :: t -> [a] (bound at temp.hs:35:9) xs :: [a] (bound at temp.hs:34:11) x :: a (bound at temp.hs:34:9) qsort' :: [a] -> [a] (bound at temp.hs:33:1) The function `m' is applied to two arguments, but its type `a' has none In the expression: m f x In a stmt of a list comprehension: m f x Failed, modules loaded: none. λ:

I read the error message, but I don't understand the reason still...

Improve this question
3
  • 3
    If you parenthesize the operators (<= and >) and surround f with backticks (`), your qsort function should then work. Backticks allow you to use binary functions like infix operators. Commented Jan 5, 2015 at 12:04
  • Yes, it works fine, thank you. But why it is necessary to use the backticks? The <= and < operators are infix operators, so I've expected infix form will works this case. Commented Jan 5, 2015 at 12:08
  • Only functions defined with "special" characters (see this) are assumed by GHC to be infix by default. As an example, try let (/./) = (+) in GHCi; you will be able to write something like 1 /./ 5 without any error. Commented Jan 5, 2015 at 12:09

1 Answer 1

Reset to default
9

You shouldn't use f as infix. You can solve it by putting f in front and representing the functions between brackets (<=):

-- third variant: qsort' :: (Ord a) => [a] -> [a] qsort' [] = [] qsort' (x:xs) = (srt (<=)) ++ [x] ++ (srt (>)) where srt f = qsort' [m | m <- xs, f m x]

This is mainly because what you basically want to do is call f on m and x. Now default lambda-calculus always evaluates first the function that is listed to the left.

Haskell only provides some syntactical sugar for operators: when you write a+b, what you basically write is (+) a b (behind the curtains). This is what Haskell likes best, but the compiler thus offers some functionality for programmer's convenience. Since writing a*b+c*d is way easier than writing (+) ((*) a b) ((*) c d), but the second is actually how to write such things in lambda-calculus.

In order to see operators as functions, you write them between brackets, so to get the function-variant of <=, you write (<=).

EDIT

As @Jubobs argues, you can also use the infix, but thus requires you to use backticks:

-- fourth variant: qsort' :: (Ord a) => [a] -> [a] qsort' [] = [] qsort' (x:xs) = (srt (<=)) ++ [x] ++ (srt (>)) where srt f = qsort' [m | m <- xs, m `f` x]

The problem is mainly you need to pass your functions through f, and <= and > aren't functions, (<=) and (>) are. Technically speaking, the story is a bit more complicated, but I guess this will suffice when learning the basics.

By using backticks, Haskell reads:

x `f` y

as:

f x y

(note that this is not completely true since operators have also a priority: * binds tighter than +, but these are more the "details" of the process).

Putting brackets over an operator is kind of the opposite effect:

x o y

is

(o) x y

with o an operator.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thank you, this works fine. But why I can't use the infix form? Both operators are the infix and I've expected infix call will work...

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.