Functional Thinking in Clojure: Part 3

Refactored Number Classifier

Neal starts his latest article demonstrating what he would have done if he’d been programming in a functional language like Scala from the beginning. Seems like the perfect place for me to do the same in Clojure.

Voila!

Some notes about what I’ve done:

1. When I originally optimized aliquot-sum, I slavishly followed (or thought I did) his implementation and thus mimicked his use of Math/round and Math/sqrt. This is cool, but then you have to add 1 to the resulting number to begin to check for factors. Why not just use the equally valuable Math/ceil function? Thus, instead of deciding which way to round based on the size of the floating point number, we just always round up as high as we can go.

2. The use of Math/round allows us to get rid of the (+ 1 … code, which makes the whole step sightly more readable, IMHO.

3. I pulled factor? out into it’s own function and now my filters read very nicely.

4. I’ve removed the slow implementation of aliquot-sum but left classify as a function who’s guts can be replaced. If someone else wants to come along with some sort of elliptic curve factorization algorithm that I can’t even begin to understand, they are officially my guests.

My implementation thinks a little differently about the problem than Neal apparently wants to, but like I said I find his implementation to be a bit repetitious.

Functional Testing

Neal begins by documenting some of the changes he thinks functional programming can bring to your testing.

I started off by copying his initial implementation as directly as I could.

1. I use map instead of a for loop, because for loops suck.

2. The #(...) construct is a reader macro that allows for very succinct anonymous function definition. I’m avoiding it more and more now that I know about partial and comp.

3. Clojure supports branching!

4. This will result in over 10,000 tests running, which is a little slower than necessary.

So I refactored immediately.

1. I didn’t like that if form in the original code. An easy way to get around that is to use the sequence manipulation functions to get a slightly more declarative solution. Now, I classify all of what I expect to not be perfect in the range 1 to 10000 and verify that none of them turned out to be perfect.

2. #{...} is the notation for creating a hash-set literal. I also apply hash-set to the range so that I can disj them.

Turns out that Neal wasn’t super happy with his implementation either, specifically because of that for loop. He transformed his thinking as well and here’s my implementation of that:

This translates pretty directly into Clojure. We’re verifying that the only perfect numbers in that range are the ones we expect via filtering. Perhaps interesting to note that = works despite filter producing a seq.

Moving on to currying.

What the heck is currying? Or, where I attempt to appear like I have the ability to ascend far above my own head.

When I got to writing this section, I realized that I have no clue what currying is and why it’s so important. I’ve heard Rich and other Clojurians say that they explicitly decided to not follow Haskell down the full currying path, but not why. I’ve heard Haskell people say that currying is so important that you cannot do anything else in their language.

So when two really smart groups of people disagree, what’s a relatively dumb one like me supposed to do?

Improvise!

As a side note, it seems much more common to not understand currying than it does to understand it. Neal doesn’t seem to understand currying, at least according to his article. For that matter, some of the other authors over at Developer Works don’t seem to understand currying. And over some brief discussions with other developer friends, once you understand currying, the most common question I found was, ‘So what?’.

For my purposes, and so this article can at the very least be internally consistent even if it’s externally wrong, Currying is taking a function of more than 1 argument and splitting it up into many functions that take 1 argument and return another function that takes 1 argument until you reach the last argument after which the result is given.

Partial application, in contrast, is not currying, though many of the authors at IBM Developer Works seem to think so. Partial application is taking a function of multiple arguments (i.e., a function that could not exist in Haskell, where all functions take exactly one argument) and ‘fixing’ some of the leading arguments, returning a new function that takes less arguments (or the same number of arguments in the case of true variadic functions like +).

The question in my head is why currying matters beyond partial application, which you can obviously see how much I enjoy by reading the code samples in this series.

One of the main advantages noted by Haskell folks in #haskell is that currying allows for automatic partial application. This is actually a good, albeit debatable, deal. It’s a question of verbosity. (comp (partial a b c) (partial d e f) (partial g h i)) is a heck of a lot more verbose than a b c . d e f . g h i. Which do you find to be more readable? How ‘bout more writable?

Notably, Scala does support auto-partial application. Pass less arguments than the function definition required and you get a new function definition back that has the first n arguments fixed and accepts the rest of the arguments. Again, this isn’t currying, but it does solve the initial point brought up by the Haskell folks. I have no idea why Clojure doesn’t do this. Why isn’t it possible to (comp (a b c) (d e f) (g h i))?

Greater minds than mine will have to explain.

I’m not happy with that argument because it comes down to an aesthetic decision, not a technical one. Doesn’t feel like that should be correct. On the other hand, I do believe strongly in aesthetics driving thought so I can see the point. I’m definitely on the side that my lovely AST is more important than complete succinctness but I understand the other side.

Another possibility is something hinted at in Learn You A Haskell, namely, that you can partially apply arguments out of order, which is something I’ve been tempted to do a lot in my own source. Turns out this isn’t really valid, as this is more a product of supporting infix notation than it is of currying your functions. Obviously in a prefix language like Clojure, infix is irrelevant and thus functions don’t have ‘sides’ that you can apply an argument to. You can get the same effect by defining an anonymous function but it’s much more verbose.

To wrap up this little tour of currying, 2 points that I understand almost not-at-all. One, several people mentioned that pointfree programming rocks. I read through the wiki page and this again seems to come down to an aesthetic decision. Two, several people in #haskell continually asked me what ‘type’ a variadic function would have, and how you would define the argument type constraints of your function in the case of variadic arguments. As a Clojure programmer, I’m not used to caring about types (unless I pass the wrong one in!), but this is apparently very important to the Haskell folks. It seems like this is for the same reason that most people argue for static type checking, namely, compiler level function call verification. I’ve obviously been won over by the dynamic language siren since I’m using Clojure, but I can see the point. This is the case where Haskell is more verbose than Clojure. It’s up to you whether that’s a good or bad thing.

Enough theory, let’s get to the code!

Neal’s ‘Currying’ examples

Now that I’ve thoroughly destroyed Neal’s notion of currying, let’s get on to exploring what he does through partial function application, which Groovy does indeed support, albeit through a method, not automagically like Scala.

I think the only thing terribly interesting here, as in new to show off, is the recursion construct that Clojure supplies. Everything else is vanilla function composition as I’ve showed off in my other posts.

If you’re not familiar with recursion, the good news is that you don’t have to be! In Clojure at least, recursion is pretty uncommon because you can accomplish much of it through list comprehension in it’s various flavors. It’s so uncommon that whenever I’m forced to do it because of a programming challenge or something like this, I always have to look it up again.

Basically, Clojure supplies easy recursion just like any other language through calling yourself within your definition. The badness here is that there is no tail-call optimization on the JVM. Thus, rather than solving that problem partially and off-loading the over-head of reasoning about whether or not you’ll blow your stack in this or that instance, Clojure simply says that you’ll never get it, unless you explicitly use the recur form. recur allows you to get the benefits of tail-call optimization on the JVM.

A couple of points:

1. recur must be used in the tail position of your function.

2. recur outside of a loop uses the function definition as it’s loop point.

3. If that doesn’t work for you, as in this case, you can supply a loop form that gives it it’s own bindings as in let.

I think that’ll do for this iteration of my Functional Thinking in Clojure series. Hopefully you’re continuing to get good stuff out of it and you’ll stay tuned for next time.