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

Answer 2

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

You can always cheat and use the "pl" tool from lambdabot (either by going to #haskell on freenode or by using e.g. ghci on acid). For your code pl gives:

((chr . (a +) . flip mod 26) .) . flip flip (2 * a) . ((-) .) . (. ord) . (+) . ord

Which isn't really an improvement if you ask me.

Answer 3

There's definitely a set of tricks to transforming an expression into point-free style. I don't claim to be an expert, but here are some tips.

First, you want to isolate the function arguments in the right-most term of the expression. Your main tools here will be flip and $, using the rules:

f a b ==> flip f b a
f (g a) ==> f $ g a

where f and g are functions, and a and b are expressions. So to start:

(\k t -> chr $ a + flip mod 26 (ord k + ord t -2*a))
-- replace parens with ($)
(\k t -> chr $ (a +) . flip mod 26 $ ord k + ord t - 2*a)
-- prefix and flip (-)
(\k t -> chr $ (a +) . flip mod 26 $ flip (-) (2*a) $ ord k + ord t)
-- prefix (+)
(\k t -> chr $ (a +) . flip mod 26 $ flip (-) (2*a) $ (+) (ord k) (ord t))

Now we need to get t out on the right hand side. To do this, use the rule:

f (g a) ==> (f . g) a

And so:

-- pull the t out on the rhs
(\k t -> chr $ (a +) . flip mod 26 $ flip (-) (2*a) $ ((+) (ord k) . ord) t)
-- flip (.) (using a section)
(\k t -> chr $ (a +) . flip mod 26 $ flip (-) (2*a) $ ((. ord) $ (+) (ord k)) t)
-- pull the k out
(\k t -> chr $ (a +) . flip mod 26 $ flip (-) (2*a) $ ((. ord) . ((+) . ord)) k t)

Now, we need to turn everything to the left of k and t into one big function term, so that we have an expression of the form (\k t -> f k t). This is where things get a bit mind-bending. To start with, note that all the terms up to the last $ are functions with a single argument, so we can compose them:

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

Now, we have a function of type Char -> Char -> Int that we want to compose with a function of type Int -> Char, yielding a function of type Char -> Char -> Char. We can achieve that using the (very odd-looking) rule

f (g a b) ==> ((f .) . g) a b

That gives us:

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

Now we can just apply a beta reduction:

((chr . (a +) . flip mod 26) .) . (flip flip (2*a) . ((-) . ) . ((. ord) . (+) .ord))