coding style - Point-free in Haskell

Question

I have this code that I want to make point-free;

(k t -> chr $ a + flip mod 26 (ord k + ord t -2*a))

How do I do that?

Also are there some general rules for point free style other than "think about this amd come up with something"?

Answer 1

To turn a function

func x y z = (some expression in x, y and z)

into point-free form, I generally try to follow what is done to the last parameter z and write the function as

func x y z = (some function pipeline built using x and y) z

Then I can cancel out the zs to get

func x y = (some function pipeline built using x and y)

Then repeating the process for y and x should end up with func in point-free form. An essential transformation to recognise in this process is:

    f z = foo $ bar z    -- or f z = foo (bar z)
<=> f z = foo . bar $ z
<=> f   = foo . bar

It's also important to remember that with partial evaluation, you can "break off" the last argument to a function:

foo $ bar x y == foo . bar x $ y    -- foo applied to ((bar x) applied to y)

For your particular function, consider the flow that k and t go through:

1. Apply ord to each of them
2. Add the results
3. Subtract 2*a
4. Take the result mod 26
5. Add a
6. Apply chr

So as a first attempt at simplifying, we get:

func k t = chr . (+a) . (`mod` 26) . subtract (2*a) $ ord k + ord t

Note that you can avoid flip by using a section on mod, and sections using - get messy in Haskell so there's a subtract function (they clash with the syntax for writing negative numbers: (-2) means negative 2, and isn't the same as subtract 2).

In this function, ord k + ord t is an excellent candidate for using Data.Function.on (link). This useful combinator lets us replace ord k + ord t with a function applied to k and t:

func k t = chr . (+a) . (`mod` 26) . subtract (2*a) $ ((+) `on` ord) k t

We're now very close to having

func k t = (function pipeline) k t

and hence

func = (function pipeline)

Unfortunately Haskell is a bit messy when it comes to composing a binary function with a sequence of unary functions, but there is a trick (I'll see if I can find a good reference for it), and we end up with:

import Data.Function (on)

func = ((chr . (+a) . (`mod` 26) . subtract (2*a)) .) . ((+) `on` ord)

which is almost a nice neat point-free function pipeline, except for that ugly composing trick. By defining the .: operator suggested in the comments on this page, this tidies up a little to:

import Data.Function (on)

(.:) = (.).(.)

func = (chr . (+a) . (`mod` 26) . subtract (2*a)) .: ((+) `on` ord)

To polish this some more, you could add some helper functions to separate the letter <-> Int conversion from the Caesar cipher arithmetic. For example: letterToInt = subtract a . ord