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"?
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"?
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.
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 z
s 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:
ord
to each of themchr
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
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))