Alan Dipert tweeted an interesting puzzle:
pop quiz: solve http://www.4clojure.com/problem/107 point-free. answer must be a function value! #clojure
The 4clojure version of the problem is simple enough, but the added requirement of a point-free solution makes Alan’s version of the problem harder. And harder to resist. So I took a shot at it.
My plan was simple: solve the problem in the natural way, and then transform the solution into the point-free style. Piece of cake. Not.
Here’s my starting place:
(fn [x] (fn [y] (reduce * (repeat x y))))
That solves the 4clojure version of the problem, but I need to get rid of the arguments x and y, and the lambdas. To make a long story short, I couldn’t do it. The best I could manage was this:
#(comp (partial reduce *) (partial repeat %))
I managed to rid of one lambda and one variable, but could not get rid of the remaining argument, now slightly disguised as %, and the remaining lambda, disguised as #().
I wanted to know the answer, so I asked Alan, who directed me to a tweet by Baishampayan Ghose. Now the story starts to get interesting. This was @ghoseb’s answer:
(partial partial (comp (partial reduce *) repeat))
Yow! I would not want to run into that in the wild. No matter how hard I stared at that code, I could not get a clear understanding of how it works. But there are methods other than staring, say abstraction and equational reasoning. Let’s use them to analyze @ghoseb’s code.
I mentioned equational reasoning, so let’s introduce a couple of equations that describe the action of the functions partial and comp.
- P: ((partial f g) x) == (f g x)
- C: ((comp f g) x) == (f (g x))
I have labelled the equations P and C, so that I can refer to them later. The equations combine infix and prefix notation. Don’t let that bother you; it’s ok to be less than rigorous in meta-language. Mathematicians do it all the time. The symbols f, g, and x are just variables.
Each equation states that two expressions are equivalent. Here are concrete examples of P and C, written in executable Clojure.
(= ((partial * 2 3) 4) ;; illustrates P
(* 2 3 4))
(= ((comp #(* % % ) inc) 1) ;; illustrates C
(#(* % %) (inc 1)) )
Now let’s put P and C to work on @ghoseb’s code. We’ll start by writing out what we know from the problem. We know, and can test by execution, that the following expression evaluates to 256.
(((partial partial (comp (partial reduce *) repeat)) 2) 16)
I mentioned that we would use abstraction; by abstraction I mean giving things names. There is one chunk of code in there, enclosed in the innermost parens, that is easy to understand. Let’s give it a name.
(def mult (partial reduce *))
The mult function applied to a finite sequence of numbers returns their product:
user> (mult [1 2 3 4])
We can rewrite our expression using mult and get a slightly simpler expression that still evaluates to 256.
(((partial partial (comp mult repeat)) 2) 16)
Next we’ll simplify a sub-expression. P allows us to infer that
;; ((partial partial (comp mult repeat)) 2) == (partial (comp mult repeat) 2)
Protip: forget the semantics for a moment, and just look at the syntax. P allows us to drop one set of parens, and one instance of partial.
Now we go back to our expression that evaluates to 256, and substitute the simplified subexpression.
((partial (comp mult repeat) 2) 16)
The P rule has been working for us, let’s use it again. Think symbolically, algebraically. Lose a set of parens, and a partial.
((comp mult repeat) 2 16)
We have eliminated all instances of partial. So let’s use C to get rid of the comp.
(mult (repeat 2 16))
This expression is easy to understand, provided you understand mult and repeat.
Just one thing. Did you buy that last substitution? I claimed above that the C rule works as follows:
((comp f g) x) == (f (g x))
But the rule I actually used was this:
((comp f g) x y) == (f (g x y))
The thing to understand is that because Clojure functions can be variadic, C is really a pattern of rules, dependent on the arity of g.
- ((comp f g) x) == (f (g x))
- ((comp f g) x y) == (f (g x y))
- ((comp f g) x y z) == (f (g x y z))
- … etc …
Similarly, P is also a family of rules:
- ((partial f g) x) == (f g x)
- ((partial f g) x y) == (f g x y)
- ((partial f g) x y z) == (f g x z)
- … etc …
The situation with P is even trickier, because we have to also account for the fact that partial is variadic:
- ((partial f g) x) == (f g x)
- ((partial f g h) x) == ((partial f g) h x) == (f g h x)
- … etc …
In general, P allows us to transform (f x1 x2 … xn) into ((partial f x1 …. xk) xk+1 … xn) for our choice of 1 <= k < n.
Something to note is that the P and C rules are bidirectional. We can take advantage of that to run the analysis of @ghoseb’s code backwards, and maybe get some insight into how to construct a point free solution in the first place.
The solution will have to implement exponentiation. Whatever the implementation, it will have to be true that ((solution 2) 16) evaluates to 256. We don’t know the details, but we see the shape of it. We can start with a fairly natural solution with the wrong shape, below, and use the P and C rules to mold the solution into the right shape.
(mult (repeat 2 16)) ;; now use C
((comp mult repeat) 2 16) ;; use P
((partial (comp mult repeat) 2) 16) ;; use P
(((partial partial (comp mult repeat)) 2) 16) :; use def of mult
(((partial partial (comp (partial *) repeat)) 2) 16)
And done. The trick, as in algebra, is to know which rule to apply when. Practice helps, as does a clear understanding of what rules apply, and why. I hope anyone who got this far finds some value in this analysis.
My thanks to @alandipert and @ghoseb for the lovely puzzle. It was instructive, in more than one way.
Years ago I made a promise to my wife that I would not allow my daughter to “check out from math”. I have kept that promise, and in so doing have tried to bear in mind that it is hard to learn to think with symbols. This fall my daughter came home first day of school with a math assignment, a variety of simple algebra problems. It was a diagnostic, the problems were nothing she hadn’t seen before, but she was out of practice after a summer off. I walked her through the assignment, but I too was out of practice. Not with the math, that I could do without thinking. And I did, without thinking. And without the patience and understanding that I should have shown. My daughter thought I was disappointed with her. My fault. This problem reminded me of what it’s like to struggle with symbolic thinking. I hacked without plan or self-awareness, and I floundered.
After I saw @ghoseb’s solution I took the time to think systematically, and was rewarded with insight. I learned a bit about programming, and a bit about humility and patience. It was a good day.