Haskell dot operator with sort and (++)

Question

I am learning haskell at the moment and trying to figure out all the rules of prefix, infix, precedence, etc.

While trying to implement a function which appends two lists and sorts them I started with:

appendAndSort :: [a] -> [a] -> [a]
appendAndSort = sort . (++)

which does no compile.

Following:

appendAndSort :: Ord a => [a] -> [a] -> [a]
appendAndSort = (sort .) . (++)

on the other hand does work.

Why do I have to add a second dot at sort and parentheses around it?

Answer 1

The expression (f . g) x means f (g x).

Coherently, (f . g) x y means f (g x) y.

Note how y is passed as a second parameter to f, not to g. The result is not f (g x y).

In your case, (sort . (++)) x y would mean sort ((++) x) y, which would call sort with first argument (++) x (the function which prepends the list x to its list argument), and with second argument y. Alas, this is ill-typed since sort only takes one argument.

Consequently, this is also invalid

appendAndSort x y = (sort . (++)) x y

hence so is this

appendAndSort = sort . (++)

---

By contrast, ((f .) . g) x y does work as expected. Let's compute:

((f .) . g) x y
=  -- same reasoning as above, y is passed to (f.), not g
(f .) (g x) y
=  -- application associates on the left
((f .) (g x)) y
=  -- definition of `(f.)`
(f . (g x)) y
= -- definition of .
f ((g x) y)
=  -- application associates on the left
f (g x y)

So this really makes y to be passed to g (and not f).

In my opinion the "idiom" (f .) . g isn't worth using. The pointful \x y -> f (g x y) is much simpler to read, and not terribly longer.

---

If you really want, you can define a custom composition operator to handle the two-argument case.

(.:) f g = \x y -> f (g x y)

Then, you can write

appendAndSort = sort .: (++)

Answer 2

Let's start with a version that uses explicit parameters.

appendAndSort x y = sort (x ++ y)

Writing ++ as a prefix function rather than an operator yields

appendAndSort x y = sort ((++) x y)

Knowing that (f . g) x == f (g x), we can identify f == sort and g == (++) x to get

appendAndSort x y = (sort . (++) x) y

which lets us drop y as an explicit parameter via eta conversion:

appendAndSort x = sort . (++) x

The next step is to repeat the process above, this time with (.) as the top most operator to write as a prefix function,

appendAndSort x = (.) sort ((++) x)

then apply the definition of . again with f == (.) sort and g == (++):

appendAndSort x = (((.) sort) . (++)) x

and eliminate x via eta conversion

appendAndSort = ((.) sort) . (++)

The last step is to write (.) sort as an operator section, and we're done with our derivation.

appendAndSort = (sort .) . (++)