Explaining Functional Programming to Eight-Year-Olds

“Map” and “fold” are two fundamentals of functional programming. One of them is trivially easy to understand and use. The other is not, but that has more to do with trying to fit it into a particular view of functional programming than with it actually being tricky.




There’s not much to say about map. Given a list and a function, you create a new list by applying the same function to each element. There’s even special syntax for this in some languages which removes any confusion about whether the calling sequence is map(Function, List) or map(List, Function). Here’s Erlang code to increment the values in List:

[X + 1 || X <- List]

Fold, well, it’s not nearly so simple. Just the description of it sounds decidedly imperative: accumulate a result by iterating through the elements in a list. It takes three parameters: a base value, a list, and a function. The last of these maps a value and the current accumulator to a new accumulator. In Erlang, here’s a fold that sums a list:

lists:foldl(fun(X, Sum) -> X + Sum end, 0, List)

It’s short, but it’s an awkward conciseness. Now we’ve two places where the parameter order can be botched. I always find myself having to stop and think about the mechanics of how folding works—and the difference between left and right folding, too (lists:foldl is a left fold). I would hardly call this complicated, but that step of having to pause and run through the details in my head keeps it from being mindlessly intuitive.




Compare this to the analog in array languages like APL and J. The “insert” operation inserts a function between all the elements of a list and evaluates it. Going back to the sum example, it would be “+/” in J, or “insert addition.” So this:

1 2 3 4 5 6

turns to this:

1 + 2 + 3 + 4 + 5 + 6

giving a result of 21. The mechanics here are so simple that you could explain them to a class of second graders and not worry about them being confused. There’s nothing about iterating or accumulating or a direction of traversal or even parameters. It’s just…insertion.




Now there are some edge cases to worry about, such as “What does it mean to insert a function between the elements of a list of length 1”? Or an empty list for that matter. The standard array language solution is to associate a base value with operators, like addition, so summing a list containing the single value 27 is treated as 0 + 27. I’m not going to argue that APL’s insert is more general than fold, because it certainly isn’t. You can do all sorts of things with the accumulator in a traditional fold (for example, computing the maximum and minimum values of a list at the same time).




But in terms of raw simplicity of understanding, insert flat-out beats fold. That begs the question: Is the difficulty many programmers have in grasping functional programming inherent in the basic concept of non-destructively operating on values, or is it in the popular abstractions that have been built-up to describe functional programming?




(If you liked this, you might like Functional Programming Archaeology.)

Comments

insert(F, [H1,H2])  -> F(H1,H2);
insert(F, [H1,H2|T]) -> insert(F, [F(H1,H2)|T]).

so insert/2 should be in the standard libraries?

:-)

Posted by anon on 11 Jul 2010 at 10:47

Pastor Melissa Scott

wonderful post.. thank you!

Posted by Melissa Scott on 16 Jul 2010 at 07:32

Add comment