The <= and > operators as a function arguments

Question

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...

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. — jub0bs, Jan 05 '15 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. — Andrey Bushman, Jan 05 '15 at 12:08
Only functions defined with "special" characters (see [this](http://stackoverflow.com/questions/10548170/what-characters-are-permitted-for-haskell-operators)) 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. — jub0bs, Jan 05 '15 at 12:09

Willem Van Onsem · Accepted Answer · 2015-01-05T13:06:17.907

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.

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... — Andrey Bushman, Jan 05 '15 at 12:04

The <= and > operators as a function arguments

1 Answers1