Functional Data Structures Out Of Nowhere
I’ve been watching the Structure and Interpretation of Computer Programs videos recently while riding the Caltrain and enjoyed it quite a bit. For some reason I can’t quite grasp, I find these fun. Maybe it’s the fact that these are 20 years old now and still terribly relevant (especially for functional programming), maybe it’s the look of the attendance, very eighties, or maybe the obvious delectation Hal Abelson and Gerald Jay Sussman have teaching. Anyways, pretty intesting stuff.
One of the thing they emphasize a lot during their lessons is the blurring line between data structures and functions when programming in a functional style extensively. The Javascript accessors overriding technique in my last post was a pretty good example of it but there’s a much better one in the video: constructing a Pair data structure out of pure nothingness. I’ve adapted it in 3 different functional languages below, just take your pick.
Javascript
[source:javascript]
js> var Pair = function(a,b) { return function(pick) { return (pick > 0) ? b : a; } };
js> var head = function(p) { return p(0); };
js> var tail = function(p) { return p(1); }
js> head(Pair(3,’b'));
3
[/source]
Ruby
[source:ruby]
irb> def make_pair(a,b)
irb>Â Â lambda { |pick| pick > 0 ? b : a }
irb> end
irb> def head(p); p[0]; end
irb> def tail(p); p[1]; end
irb> tail(make_pair(8, :foo))
=> :foo
[/source]
[source:ruby]
arc> (def make_pair (a b) (fn (pick) (if (> pick 0) b a)))
arc> (def head (p) (p 0))
arc> (def tail (p) (p 1))
arc> (tail (make_pair ‘a ‘b))
b
[/source]
It’s a very good illustration of how to introduce data structures in any functional language. Once you have a pair, you have a list. Once you have a list, you have a hash. I won’t argue that those would probably be a few order of magnitude slower than data structures mapped directly in memory but still, it sort of turns the world upside down. Instead of having objects that are bags of functions, you have functions that operate on something that feels like an object.
The implementation is of course a bit awkward, using this little pick parameter to select the right value in the closure. But that’s not the point, if I were to tell you that I’ve made a Pair API for you with a way to build a pair, get its head and its tail, the way it’s programmed would be irrelevant to you. I can change my implementation anytime without you even noticing. The abstraction is complete.
Photo (and painting) by Rob Lee
Matthieu Riou on March 3rd 2008 in Uncategorized
greg responded on 03 Mar 2008 at 9:32 am #
You have a typo in the arc example. Should be “(def tail …)” not “(def tails …)”.
Cale Gibbard responded on 03 Mar 2008 at 9:50 am #
The usual way to encode a pair with functions isn’t quite what you have here though. The usual encoding is to take the two parameters x and y and produce a function which when applied to some function f will apply f to x and y. The functions for extracting the first and second part will then simply apply the given pair to a function which simply returns its first or second parameter.
There’s no need for numbers here!
Matthieu Riou responded on 03 Mar 2008 at 11:27 am #
@greg: thanks, that’s fixed.
@Cale: Yes, there are quite a few different ways to implement this. I decided to stick with the one proposed by GJS because it’s maybe more clear to untrained functional eyes. Also its slightly hackish feeling illustrates the last point that implementation can be improved anytime without leaking. But I certainly agree the implementation you proposed is more elegant. Care to post a little snippet in your favorite language for others to see?
Stevan Little responded on 03 Mar 2008 at 2:15 pm #
If you are looking for a more pure Lambda Calc approach, you could start with some Church Booleans and then use those to build your pair with. Here is an example of that using Perl
# TRUE := λ x. λ y. x
sub TRUE {
my $x = shift;
sub { $x }
}
# FALSE := λ x. λ y. x
sub FALSE {
my $x = shift;
sub { shift }
}
# pair := λ f. λ s. λ b. b f s
sub pair {
my $f = shift;
sub {
my $s = shift;
sub {
my $b = shift;
$b->($f)->($s);
}
}
}
# head := λ p p TRUE
sub head {
my $p = shift;
$p->(\&TRUE)
}
# tail := λ p p FALSE
sub tail {
my $p = shift;
$p->(\&FALSE)
}
From here you can implement lists and so forth.
- Stevan
James Tauber responded on 04 Mar 2008 at 1:08 am #
Stevan,
Typo in your comment on FALSE. Should be
# FALSE := λ x. λ y. y
Kevin’s Link Blog » Functional Structures responded on 04 Mar 2008 at 2:32 am #
[...] Functional Structures Out Of Nowhere [...]
Christophe Grand responded on 04 Mar 2008 at 3:53 am #
What Cale suggests, in js:
# js> var Pair = function(a,b) { return function(pick) { return pick(a, b); } };
# js> var head = function(p) { return p(function(a) {return a}); };
# js> var tail = function(p) { return p(function(_, b) {return b}); }
# js> head(Pair(3,’b'));
Eddie Welker responded on 04 Mar 2008 at 5:58 am #
Those videos are fun, I’ve been watching them intermittently for a couple of weeks now. I think it is the fact that they’re still relevant… and from an era where things were vastly different.
Anyway, haven’t gotten to this lecture yet, but I’ll be sure to revisit when I do.
jonathan responded on 04 Mar 2008 at 7:39 am #
Very interesting. Python version:
>>> def Pair(a, b):
… return lambda pick: b if pick > 0 else a
>>> def head(p): return p(0)
…
>>> def tail(p): return p(1)
…
>>> head(Pair(3, ‘b’))
3
Sp3w » Blog Archive » Linkage 2007.03.05 responded on 05 Mar 2008 at 8:37 am #
[...] Functional Data Structures out of Nowhere [...]
Off The Lip » The Problem With Assignment responded on 21 Apr 2008 at 6:20 am #
[...] again (please bear with me for a moment even if this sounds like my last post), a good start would be a purely functional definition of pairs and the corresponding extraction [...]
-= Linkage 2007.03.05 =- responded on 26 Jan 2009 at 7:38 am #
[...] Functional Data Structures out of Nowhere<br/> [...]