tommorris.org

Discussing software, the web, politics, sexuality and the unending supply of human stupidity.


functional programming


Code noodling contest: functionalize this

Learning moment for me. I’ve been learning functional programming for a while, but was faced with an interesting little challenge today. I’ll spare you the problem domain, which is rather boring, and simply give you what’s needed…

A function that takes a positive (that is n>=1) integer, calculate the number of times this number is divisible by 16, and how many times the remainder is divisible by 8, and how many times the remainder of that is divisible by 4, and how many times the remainder of that is divisible by 2. Return each of these values in a key-value structure similar to Ruby’s Hash.

My mind immediately leapt to “oh, this is a perfect fit for some kind of functional technique! Who needs variables?” And then I sat down and tried to write something and my brain very quickly turned to jelly, and I gave in and wrote a very quick imperative version.1 Which looks like this:

Which is fine and will do the job. But, here’s the challenge to any of my FP-loving readers. Feel free to code-golf the hell out of this. Lisp/Clojure, Scala, Haskell, OCaml, Ruby, Python, JavaScript: whatever your poison, show me how much I suck for using variables. The prize? I might nick your solution and quietly put it into production. And you get over 9000 nerdpoints. And the warm feeling of satiating my curiosity. I don’t care if you don’t output necessarily the same data structures, but you do have to output the right values given the same input.2

  1. Why? My new standard practice with the client in question is to sit down with them at a computer, and if they describe some potentially complex business rule, try and write a simple implementation of the rule in the form of a Ruby (or Python or Scala or whatever) function and verify that it does vaguely what they want. I then chuck it in the bug tracker so when I implement it, I have some nice readable, compilable pseudocode rather than a vague specification. In many cases, implementation is just a matter of writing tests, putting it in the context of the class, documenting and updating the UI and so on.

  2. If you feel like cluttering your example code up with checks to make sure non-positive non-integers raise an exception, feel free. But that’s not really what I’m interested in.


Folding in Ruby and Scala

I’d like to think I’m no slouch at functional programming, but I came across a nice little example today of where Ruby’s functional programming features weird me out: inject.

Consider a perfectly simple example of where functional programming would be useful: summing an array of objects of the same type that all have a property or method that returns an integer value.

Here is how one might do it in Java (or C, PHP or another language without the benefit of higher order functions):

That’s easy enough. You might need to deal with what happens the length value is nil, and you might need to handle exceptions. Whatever.

But, of course, functional programming is here to make your life better. You shouldn’t need to write the same foreach-accumulator code every time for every different property. So, imagine if we had an array of objects that had five different properties that are all integers: length, height, weight, smelliness. We want to sum them all, or average them all or whatever. This is where higher-order functions become so useful.

In Scala:

Okay, now imagine we’ve got something similar in Ruby. The code transliterates reasonably well.

Two nitpicky things here about syntax:

  1. The map syntax is simpler in Scala: I’ve always found “and-colon” in Ruby to be a rather ugly and unreadable construction. I understand it alright, but I’m not confident that Ruby newbies understand it. (But, then, lotsa Ruby newbies don’t grok functional programming: I certainly didn’t.)
  2. The word “inject” is a bloody strange word for a well-understood concept: every other language with fold-left calls it fold-left (or foldLeft or foldl or fold or something similar involving the word “fold”). “inject” is eminently forgettable.

I could, of course, monkey patch in “fold_left” as an alias to inject.

Here is where it gets more interesting for Scala though. The type system lets you do type-dependent monkey patching.

Consider the generic concept of folding or reducing values: it is simply a process where you turn numerous values of the same type into a unified result of a particular type. So, summing is a folding operation, as is producing a mean, a mode, a median etc.

Enter Scala implicits.

Now one can do something like this…

How does this differ from just monkey patching ‘sum’ into Ruby’s Array class? It only applies to lists made exclusively of one particular type: Ints. Implicits let you target specific types in a way that Ruby monkey patching doesn’t. This is pretty powerful, and yet another reason to learn to love static typing.

You can call sum on List[Int] but not on List[String] (unless you define a new class that implements a sum method and an implicit conversion function for List[String]). Without one of those, you’ll get a type error if you call something like the following:

Think about the power of this: programming often boils down to doing some repetitive action to a list of values of the same type. In Ruby, you can monkey patch the individual class, but think about how you can make code more readable by adding methods to both the objects and the collections of objects, without those modifications spilling out and affecting collections of objects of other types.

I think this is a real example of where Scala’s static type system combined with implicits and functional programming allows for a far more expressive way of coding.


On learning functional programming

Functional Scala: Introduction is a pretty good introduction to functional programming.

For me, learning functional programming was a very strange thing because I did it almost completely unconsciously. I learned Ruby, where using a for loop rather than an each method is just not done very often. Then you start using closures for callbacks, event loops and the like, and it all just naturally falls into place without much thinking at all. I found with Ruby, learning functional programming wasn’t like sitting down and learning functional programming, any more than if you use Java/C/whatever you sit down and think “I want to learn imperative programming”.

When you learn functional programming through Ruby, you don’t think “gee, I’m passing around a closure which is a function without a name and is a piece of data and I’m not modifying state and bla bla”. No, it is much more subtle and corrupting! You just see “oh, each is like for. When I want to write a for loop, I write an each loop.” And you don’t learn the theory behind it at first, until it suddenly clicks what is going on. And then you abstract a bit away and do a each(&:foo) call and you see the power of it.

Then you sort of think, “well, all the crazy kids on Hacker News are hyping this up like it is the second coming of Jesus, I better have a look and see what I haven’t understood”.

And you go and read a tutorial on functional programming and you read all these comments about how radically different it all is, and you read code samples in Haskell with super-tight tail-call-optimized recursive Fibonacci implementations or how much more awesome qsort is in OCaml or F# or Scala or whatever.

And, yes, if you are a mathematically-minded person writing the sort of code where one wants to write code that looks and feels like a maths textbook, that’s fine. But it never quite seems real.

What nobody seems to ever show is an example of a large programme: I’m not talking about an enormous 50m line Java-esque monstrosity with heaps of AbstractFactoryFactory crud. No, it’d just be nice if someone were to explain how one goes from the ‘look at this sexy syntax and type inference magic’ through the ‘wow, higher-order functions are great’ to actually writing useful stuff in these languages.

This is rather why I like Scala. Although there are pesky things like the backwards-incompatible changes to the collections framework between 2.7.7 and 2.8.x, and the frankly bloody annoying mismatch between inheritance and auxillary constructors which can really make refactoring painful, the learning curve isn’t too steep and the path one takes to learning Scala is littered with what basically amount to free cakes. You can start writing Scala like Java,1 and you’ll get the benefit of it just having a nicer syntax. You get to write better OO code: you can use traits, case classes and the like. You get nice toys like scala.xml and the pimp my library pattern (is it a pattern now? This is basically Ruby’s monkey patching adapted for static typing aficionados).

But then you slowly start getting seduced with vals and closures and that apply method, and before you know it your software is filled with singletons with complex apply functions that return functions that return functions which return functions which return immutable data structures. And you’ve snuck all that into some monstrous Java enterprise system, and nobody really knows because it is just a war file. That’s the theory anyway.

I’d love to hear other experiences of what it has been like to learn functional programming or suddenly realising that despite not knowing big words like ‘referential transparency’, you already know FP.

  1. .NET translation: You can write C# like you write Java or C, but if you delve further, there’s so much more! And then there’s F# and Microsoft have put money into improving the Scala .NET implementation…