[Haskell wikibook] Article ANN: Theseus and the zipper

apfelmus at quantentunnel.de apfelmus at quantentunnel.de
Tue Feb 20 15:05:47 EST 2007

David House wrote:
> Seems like a weird point to break convention on, so I've changed it to
> use camelCase.

Ah, you're right, it doesn't look confusing at all :)

>> Well, this is too simple :) Without an extra parameter, why would you
>> want to run around and look at the subtrees? I mean, there's nothing
>> interesting at their top.
> To solve the maze? Sure, there's nothing to look at on the way, but
> you're trying to write a computer program maze here, the point of
> manipulating Labyrinths is to get to the end! :) Which makes me think;
> we could do with a Center constructor to indicate the end of the
> labyrinth.

Can be quite difficult to run around in a completely dark labyrinth :) I
also intended the extra parameter to hold (x,y)-coordinates for the
nodes to allow north-east and so on. In the picture, the concrete
labyrinth and the abstract structure look quite different.

>> Reading your remarks, I agree that the explanation of the first example
>> needs improvement. But I'd not showcase a second example. I mean, in the
>> end, the reader can only learn to construct a zipper by constructing one
>> himself, not by being showed how to construct one. Of course, he cannot
>> do the construction if he gets stuck with the showed example.
> I'm in fairly strong disagreement here. The example of a single zipper
> may not suffice, just as one explanation of a complicated concept will
> never do for everyone. People need to look at things from different
> points of view, to see an example of this, an example of that which
> are slightly different. It'd help in several ways:
> 1) Allow a different point of view of explanation (which is also why I
> favour breaking from the narrative).
> 2) Allow the reader to grasp which features are specific to the
> labyrinth zipper and which ones are part of the general concept of
> zippers.
> 3) If the reader fully understood the concept from the first example,
> it'd provide a useful way for them to confirm what they know: they can
> skip through, thinking 'Yes, that makes sense', 'Yes, I see why that's
> there', etc.
> 4) If the reader mistakenly thought they had understood the first
> example, it'd hopefully illustrate their error.
> If you see breaking the narrative as a strong disadvantage of a second
> exposition, then I appreciate your point, but I still think the
> article could elegantly hang together intertwined with dialogue. Many
> texts already take this approach, e.g. Hofstadter's "Gödel, Escher,
> Bach" and Why's "Poignant Guide to Ruby". A second example with some
> different explanations not bound by the constraints of dialogue would
> sit nicely just before the chronologically separate bit at the end,
> which would be a really nice way to round off the section. This
> approach certainly has my vote.

Mh, the second example would have to be quite different then to achieve
the effect and to be worth breaking the narrative. I intended the last
"lift a finger" picture be something like that. Perhaps it's best if I
improve the explanation and we return to the discussion afterwards? I
have to find some free time, though, so you may have to wait a bit. But
hopefully, the zipper won't run away :)

>> I understand that you want a small 'movie' showing a short walk into the
>> zipper? That's a very good idea, I'm going to create one by overhauling
>> the picture from 5).
> Not what I meant, no. I mean just a normal picture with one element
> highlighted (say, with a red circle around it), which you then go on
> to construct the zipper for. I'm not sure a movie is necessary, and it
> would be a weird and jolting change in medium.

I mean a movie that doesn't move :) A comic, so to speak.

>> And don't worry, there is enough material for the "Algebra of Data
>> Types" to explode :) (sums and products, (polynomial) functors,
>> F-algebras, coalgebras, universal properties, fixed points (inductive
>> and coinductive), etc.)
> Tasty :) Something I know little about, but sounds great. Any papers
> for background reading?

Personally, I read


but it's huge and I actually skipped most of it. The most interesting
point was the meaning of "F-Algebra". Otherwise you may skim through


but there is indeed a need for a good tutorial.

>> Indeed, the explanation of what a 'one-hole context' is is a bit thin,
>> but I'm unsure about how to make it larger. Maybe this is because I'm
>> already accustomed to use the word functor in the sense of
>> 'datastructure parametrised over a type'?
> I quite like the explanation in my quote: a structure with one value
> removed and replaced with a placeholder. I think you need to provide
> this kind of intuition before the similarities with differentiation
> become clear.

Mh, yes. "A one-hole context of the data type \mathit{Tree}\, X is
almost a value of type \mathit{Tree}\, X, but exactly one occurrence of
an X is replaced by a hole. Inserting an item of type X into the hole
gives back a completely filled \mathit{Tree}\, X. Thus, the hole acts as
a distinguished position, a focus." is not as clear, but the placeholder
is not quite correct. I'll rework that.


More information about the Wikibook mailing list