17.11.09
A list is an odd creature
I mentioned to my first-year students that a list is an odd creature: it has only a head and a tail, where the tail is itself a creature with only a head and a tail, and so on. I challenged them to produce a picture, and Saulius Lukauskas came up with this:
I have just remembered your request for a picture of a creature, with lots of heads and a tail.
The closest to this I was able to come up is a shark eating another shark eating ... etc.
Let's think of shark's head as an element in the list. This way one could think of ":" as shark teeth 'connecting' to other shark (Cons even look like a mark from a bite!). Then the head of the smaller shark is the head of new list, and the tail of the list is the bigger shark.
If we assume that water is [], then it also works in the bottom case with no elements in the list (no sharks) - only water. And water swallows the shark up to it's head so this also work (shark : []).
Comments:
<< Home
Hm. If the intuition is that x:[] is an x being eaten by water, then it might be a good idea to flip the picture horizontally, so that the left-to-right direction of the sharks agrees with the dicrection of the list cells?
On the other hand, thinking about the in-memory representation of lists it's perhaps more accurate to say that x:[] is an [] being eaten by a (x:). Then the base case does not correspond to a situation involving sharks though.
Tricky.
On the other hand, thinking about the in-memory representation of lists it's perhaps more accurate to say that x:[] is an [] being eaten by a (x:). Then the base case does not correspond to a situation involving sharks though.
Tricky.
"cons" is the list constructor but, of course, sharks with their sharp teeth are more likely to be destructors!
I taught a Scheme class using giant paper clips and index cards to illustrate list construction. That worked pretty well. I'm just glad that programming generally involves less blood and likelihood of extreme bodily harm than my second-choice career path, recursive shark fishing!
Post a Comment
<< Home
