March 2013

From Imperative to Functional: how to make the leap (Old)

Many programmers find functional programming difficult, if not downright cryptic. This is because functional programming is not merely about relinquishing the assignment statement and using closures liberally. It’s a whole different mindset.

The functional mindset

…basically boils down to three things:

Your program isn’t about what it does, but about what things are.
Your code isn’t just a linear sequence of instructions, but a tree of nested expressions.
Functions are ordinary mathematical objects, just like an integer is.

Descriptive mindset

Compare the following definitions:

// C(++)             │    -- Haskell
                     │
int square(int n)    │    square :: Int -> Int
{                    │    square n = n * n
  return n * n;      │
}                    │

Even though the two definitions above are strictly equivalent, they are very different in spirit:

The C code reads like a procedure to follow: “return n times n to whoever called you”. (I’m anthropomorphising square() here, because that’s how the imperative mindset often operates).
The Haskell code reads like a description: “the square of n is n times n”.

Don’t be fooled by this apparent simplicity. In functional programming the descriptive mindset is mandatory. If you stay stuck into the active mindset, not only will you miss the assignment statement dearly, but the other difficulties (reading order and first class functions), will be almost insurmountable.

Reading backward

Functional code is rarely a sequence of instructions that one can read from top to bottom. On the contrary, it often it looks like reversed imperative code:

// C(++)              │    -- Haskell
                      │
int compute(int n)    │    compute :: Int -> Int
{                     │    compute n = baz (bar (foo n))
  int x = foo(n);     │
  int y = bar(x);     │    -- alternate definition
  int z = baz(y);     │    g . f   = λx -> g (f x)
  return z;           │    compute = baz . bar . foo
}                     │

In the Haskell code, the data flows from right to left, instead of from top to bottom. That’s also the case for the alternate definition, which works like Unix pipes, only reversed. Now it is possible to write the Haskell program that will naturally read from left to write:

x |- f  = f x
compute = foo |- bar |- baz

The natural reading order of the program actually depends on the composition operator. It can get confusing, so I’d advise to stick to idiomatic conventions, and keep your definitions short. Really short. Less than 5 lines most of the time, rarely more than 10.

It’s not that difficult once you have adopted the descriptive mindset. Recall that a functional program is made up of nested expressions. Every expression describes something. You can give that thing a name and make it a function:

-- before                        │    -- after
compute n = baz (bar (foo n))    │    wiz     n = bar (foo n)
                                 │    compute n = baz (wiz n)

And keep using the descriptive mindset. The active mindset expects a list of actions to perform. It would be weird to read such a list other than top to bottom or left to right. The descriptive mindset doesn’t expect such a list, but something like artifact which doesn’t have to be looked at in any particular order. Just look how the different pieces are put together.

First class functions

While the above is very important, it’s only a warm up compared to first class functions. If there is one thing in functional programming that sends imperative minds running and screaming into the night, it’s those.

Please don’t.

The trick is to remember that a function is a mathematical object like any other. Making it “First Class” doesn’t elevate it to some holy rank. It actually makes it just as ordinary as an integer. See for instance:

-- with integers     │   -- with functions
                     │
next :: int -> int   │   (.) :: (b -> c) -> (a -> b) -> (a -> c)
next n = n + 1       │   g . f = λx -> g (f x)

(In case you haven’t deciphered the dot operator, it describes function composition.)

So, just like integers, functions can

be expressed literally (see 1 vs λx -> g (f x));
be passed around as arguments (see n vs g and f);
and be returned from functions (see n + 1 vs λx -> g (f x)).

Now why would we do that? The answer is, you already do.

Object oriented languages such as C++, Java, or Python have this nice thing called “polymorphism”, which in this context means that when you pass around an object, its actual behaviour may not be determined at compile time. This is achieved through inheritance and method overloading. This can be a great mechanism for code reuse, but it’s quite cumbersome.

The functional approach is more direct. Instead of manipulating whole objects, they pass around the behaviour (a function) directly. With syntactic support from the language, this is way more straightforward, and enables a number of powerful idioms. Like writing your own loops.

Imagine for instance that you want to process lists in Haskell. First, we need to define what is a list (let’s pretend it’s not in the standard library):

                              -- A List is either
data List a = Empty           -- an empty node,
            | Cons a (List a) -- or a cons cell

Now let’s process the list

inc-all :: List Int -> List Int
inc-all Empty      = Empty
inc-all (Cons e l) = Cons (foo e + 1) (inc-all l)

dbl-all :: List Int -> List Int
dbl-all Empty      = Empty
dbl-all (Cons e l) = Cons (foo e * e) (inc-all l)

See how much they have in common? With first class functions, we can easily factor that out:

map (a -> b) -> List a -> list b
map f Empty      = Empty
map f (Cons e l) = Cons (f e) (map f l)

Note that the first argument is a function, hence the (a -> b) between parentheses. Now we can go back the two functions I actually need:

inc-all l = map (λe -> e + 1) l
dbl-all l = map (λe -> e * e) l

Haskell can make it even more concise, with what we call partial application. It is not obvious from the syntax, but Haskell functions only have one argument. Multiple arguments are emulated by returning functions. Here are for instance three equivalant definitions of the addition:

add :: Int -> Int -> Int
add x y = x + y

add :: Int -> (Int -> Int)  -- the parentheses don't matter here
add x = λy -> (x + y)       -- because '->' is right associative

add :: Int -> Int -> Int
add = λx -> (λy -> (x + y))

So, inc-all and dbl-all above can be written thus:

inc-all = map (λe -> e + 1)
dbl-all = map (λe -> e * e)

Very simple, but without the fundamentals I just gave, one hardly stands a chance at deciphering it. Never mind real world functional code, it’s just too different from the imperative equivalent. It’s not harder, though. On the contrary, it is simpler most of the time. The only real difficulty is changing your mindset.