Heads and Tails in Functional Programming

January 5th, 2009 Posted in functional programming, humane, programming languages

The other night I went to the first meeting of the PDX SICP Study Group down the road in The Beave. It was nice to finally be minutes away from a programmers meeting! (I live in the boonies.) I’m sure all future meetings will be on the east side now that I’ve said that.

I’m still a functional programming n00b. Which is funny to think about, because I probably know more about FP at this point than I knew about OOP many years ago when I was a junior programmer and considered myself something of an OO expert.

FP newbie or not, I’m still an experienced programmer with my own aesthetic sense of what qualifies as good code. One of the things that has always annoyed me about LISPs is their antiquated use of car and cdr as function names. Certainly once you’ve seen them enough you know exactly what they are and what they do. But as far as skimming code goes, they are awful. They aren’t clear or intuitive to new or casual readers. Even pronouncing cdr annoys me. (I want it to be ‘cedar’. Instead it is ‘could-er’ which sounds like a character from the Dukes of Hazzard.) I feel compelled to wrap them in my own functions just to make friendlier names like ‘first’ and ‘rest’, or ‘head’ and ‘tail’.

Other languages do use the head and tail metaphor directly. Erlang, which I enjoy programming with quite a bit, has an idiom where the head and tail metaphor shows up in the naming convention but not directly in syntax or function names. Instead of extracting the first item in a list with car and the rest of the items with cdr, you unpack the list with a pattern:

Eshell V5.5.5  (abort with ^G)
1> [H|T]=[1, 2, 3].
[1,2,3]
2> H.
1
3> T.
[2,3]

(Btw, Erlang’s pattern matching is far more powerful than I’m letting on here, and it makes this simple head/tail stuff look like child’s play.)

By convention it is understood that H stands for Head, and T for Tail. And that’s fine, but what this idiom often means is that you end up declaring two or three variables for what essentially are views on a list. For example, during the SICP study group we solved a “change making” problem from Ch. 1. Here’s the code I wrote in Erlang. I opted to replace H and T with domain-specific names:

-module(change3).
-export([find_variations/2]).
-export([count_change/1]).

find_variations(0, _) -> 1;		% No amount given.
find_variations(_, []) -> 0;	% No coins given.
find_variations(Amount, _) 		% Amount is impossible.
	when Amount < 0 -> 0;

find_variations(Amount, [Coin|Rest]=Coins) ->
	find_variations(Amount, Rest) + find_variations( (Amount - Coin),  Coins).

count_change(Amount) ->
		find_variations(Amount, [50, 25, 10, 5, 1]).

The spot of interest here is the find_variations method matching [Coin|Rest]=Coins. This creates 3 variables which are, respectively, the first item from the list, the remaining list, and the original list itself. All of which get used in the function.

While I *looooove* the pattern matching in Erlang which allows these fairly clear variables to exist, I wonder if there might be a symbolic way to decorate the list variable to yield a particular view instead of requiring three separate variables to deal with. I came up with a few ideas, but I’m not sure I like any of these. Feedback is appreciated.

Idea 1 – Graphically show head and tail

Head: << List
Tail: List <<

Idea 2 - Borrow from Regex Anchors

Head: ^List
Tail: List$

Idea 3 - Misappropriate Perl's sigils

Head: $List (since the head is basically a scalar)
Tail: @List (since the tail is a list)

All of these suck in their own way, but I think I like Idea #3 the best because it gives you the opportunity to treat a list in reverse without having to reverse it first:

Last item in list: List$
All items in list except last: List@

If Erlang had a syntax like this (and thank god it doesn't), here's what that earlier function would look like, rewritten using syntax #3:

find_variations(Amount, Coins) ->
	find_variations(Amount, @Coins) + find_variations( (Amount - $Coins),  Coins).

I'd like to know what others think about this.

In closing, I'd like to note that Python, my day-to-day language, already has this flexibility using list slices:

def find_variations(amount, coins):
	return find_variations(amount, coins[1:]) + find_variations( (amount - coins[0]),  coins)

Unfortunately, Python is designed to discourage recursion so this is sort of misleading. You wouldn't write a real solution this way in Python.