[Haskell wikibook] Article ANN: Theseus and the zipper

[apfelmus at quantentunnel.de]

David House wrote:
> 1) Any reason you're not using the standard camelCase?

Not really, but I wanted to avoid any confusion between the constructor
TurnRight and the function turnright.

> 2) Any reason the maze datatypes take an extra parameter? For
> simplicity, I'd have expected:
> 
> data Node = DeadEnd
>            | Passage Node
>            | Fork Node Node

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.

> 3) You could do with splitting the first section into various
> subsections, it's a bit long and unwieldy as-is.

Yes, subsection are a good idea. As of now, Gwen already did a split.

> 4) I'm not sure I like the typesetting of the conversation using lots
> of <br>s, but I can't think of a better way of doing it off the top of
> my head.

Yeah, I'm not happy about it, too. The article in the "Scientific
American" did the same, but as there were multiple columns, it looked
better.

> 5) I don't really get this picture:
> 
> http://en.wikibooks.org/wiki/Image:Laybrinth-Zipper.png
> 
> Is the red bit meant to be one long, straight arrow?

No, it was intended to show the same red thread as Labyrinth-Thread.png
does. But it's probably very misleading.

> 6) I don't think you spend enough time with the zipper concept. I
> found when I read Huet's paper that zippers were one of those
> brain-exploding concepts, perhaps because everything is stored
> backwards. A few suggestions that would have helped me:
> 
> * We store the entirety of the labyrinth in any zipper; by zipping all
> the way to the top so that the focus is at the entrance, the
> sub-labyrinth is the whole labyrinth. The reason this is done is so
> that we can backtrack and take an alternate path at any point.
>
> * We definitely need to show a zipper for another datatype, perhaps
> binary trees. I suggest with this one, we break the narrative and
> explain step by step what each constructor means. Something like the
> following:

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'll think about how to improve the explanation and I'm confident that
it can even be fit nicely into the narrative.

> The best way is probably to give an example
> BinTree in a picture, pick one element out, display the zipper for
> that element and explain what it means. This sound like a good plan?

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).


> The second section, then:
>
> 1) Formatting: IMO it'd look better if the formulae were left-aligned.

Mh, there is one multi-line equation with a wrong center alignment. But
for the others, well, I don't know. Perhaps they should be centered but
keep aligned equality signs? Unfortunately, wikibooks do not yet provide
the good typographic quality of a book, so tuning things to look better
is rather vain at the moment.

> 2) It's currently sitting a little oddly. I think the way to take this
> is to write an 'Algebra on Datatypes' article which explains what 1,
> 0, +, * etc. mean in the concept of types and also show some
> elementary results like distributivity of * over +, c.f. normal
> algebra, and so on. We would also need to explain isomorphisms as
> they're really important but we can't really assume them.

Yeah, the material heavily relies on a not yet written chapter
"Haskell/Generic Programming" :) I prefer your name "Algebra of Data
Types", also because it's narrower in scope.

> Then we link to that article as essential background reading before
> tackling the zippers bit. We should also move the differentiation bit
> to the Algebra on Datatypes article, which would enable the focus in
> the zippers article to remain a bit more; at the moment there's
> something of a discourse at the beginning of the second section.
> Nearing the end of the AoD article we would link to the Zippers
> article and say 'Check out a really cool development of this'.

I'd leave the differentiation near the zipper because the zipper is
currently the only motivation for differentiating at all. It would be
unfortunate to present it in an abstract way. But I guess this already
happened? I think this can be remedied by inserting a section about how
the zipper hints differentiation before the introduction of one-hole
contexts.

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.)

> 3) The notion of a 'one-hole context' isn't fully explained; it's an
> odd concept to begin with and we don't really develop it enough. We
> should say something like 'Imagine a datastructure parameterised over
> a type, like trees, lists etc.. If we were to remove one of the values
> of this type from the structure and replace it with a placeholder
> indicating we've just removed something, we obtain the one-hole
> context for that removed object.', then back it up with examples,
> like:
> 
> data ListHole a = LH [a] a [a]
> data TreeHole a = ...

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'? For me, the differentiation
rules somehow do explain what a 'one-hole context' is, because they
provide unending examples.

> Then we launch into the discussion about the algebra, then we say
> something like:
> 
> "Look! The zipper for an A is just the one-hole context plus an A! You
> may have already spotted that from our examples of one-hole contexts
> earlier. It also makes sense; the one-hole context is a structure
> missing an A, so couple that with an A and you can get the original
> structure back, but this one object is singled out, focussed. Sounds
> like a zipper."

There is a very subtle point, namely that the zipper is not the
derivative of a data type (plus A). This coincidence is for special
cases only. Maybe I should clarify this even more in the text?

> Let me know what you think of these ideas. I should also point out, as
> Eric commented, that this is a really creative and different tutorial;
> it's got its limitations but I think this could be another great
> 'Killer article' to add to our repertoire. Great work!

Thanks for the comments and for the laud :)


Regards,
apfelmus