Operators <= and> as function arguments

Question

Operators <= and> as function arguments

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 can see that the functions left

and are right

almost identical. So I want to rewrite it shorter ... Something like this:

-- 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 am getting 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 still don't understand the reason ...

+3

haskell

Andrey Bushman 05 jan. 15 at 11:54

source share

1 answer

Willem van onsem · Accepted Answer · 2015-01-05T11:59:00+0000

You shouldn't use it f

as an infix. You can solve this by putting f

in front and introducing functions between parentheses (<=)

:

-- 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 you basically want to make a call f

to m

and x

. Now, by default, lambda-calculus always evaluates the function listed on the left first.

Haskell only provides syntactic sugar for operators: when you write a+b

, what you mostly write is (+) a b

(behind the curtains). This is what Haskell likes, but the compiler thus offers some functionality for the convenience of programmers. Since writing is a*b+c*d

easier than writing (+) ((*) a b) ((*) c d)

, but the second is really how to write things like this in lambda calculus.

To see operators as functions, you write them between parentheses, so to get functional, <=

you write (<=)

.

EDIT

As @Jubobs states, you can also use infix, but you need to use backlinks to do so:

-- 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 that you need to pass your functions through f

, and <=

and >

are not functions, (<=)

and (>)

. From a technical point of view, the story is a little more complicated, but I think that will be enough when learning the basics.

Using back signals, Haskell reads:

x `f` y

as:

f x y

(note that this is not entirely true, as the operators also take precedence : they *

bind harder than +

, but this is more "details" of the process).

Placing parentheses above a statement is kind of the opposite effect:

x o y

is an

(o) x y

with the o

operator.

Operators <= and> as function arguments

More articles: