On 19/02/07, Eric Y. Kow wrote:

i'm almost tempted to mail huet himself ;-)

Why not?! Once we get it cleaned up and ready, that's definitely something we should do. -- -David House, dmhouse@gmail.com

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

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 http://www.cs.chalmers.se/~patrikj/poly/afp98/ 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 http://haskell.org/haskellwiki/Research_papers/Generics 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. Regards, apfelmus