Point-free in Haskell

问题:

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"?

回答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

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

回答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))

回答4:

I am assuming that the point of your point-freeing is to make the code more concise and more readable. I therefore think that it is wise to also do some other refactorings towards simplification which then might make it easier to remove the variables.

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

First of all, the flip is unnecessary:

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

Next, I would use name and conquer to factor out an independently usable subfunction:

encode_characters k t = chr $ encode (ord k) (ord t)
encode x y = (x + y - 2*a) `mod` 26 + a

I also gave a name to the first expression to make it clearer and reusable. encode_characters is now easy to make point-free using the technique from @Nefrubyr:

encode_characters = chr . encode `on` ord

As for the second expression, I cannot produce a form that's more readable than any shown in the other answers and they're all less readable than the point-wise form. I would therefore suggest to stop refactoring at this point and admire the cleanliness and reusability of the resulting code.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

PS: as an exercise, depending on the context of the problem, some slight modification of the function interfaces (what data in what form is passed into the functions) might yield more simplifications by generalizing the problem.

A. Implement and simplify function encode_n_characters :: [Char] -> Char where encode_characters k t = encode_n_characters [k, t]. Is the result simpler than the specialized two-argument function?

B. Implement a function encode' defined via encode' (x + y) = encode x y and reimplement encode_characters using this function. Does either of the functions become simpler? Is the implementation simpler overall? Is encode' more or less reusable than encode?

回答5:

Connect on IRC, #haskell, and ask lambdabot !:

<you> @pl (\k t -> chr $ a + flip mod 26 (ord k + ord t -2*a))
<lambdabot> [the answer]