Learn you a Haskell: Zippers

by voxcogitatio • 16 years ago

49 13 16 years ago

jberryman• 16 years ago

LYAH is great. For those who are interested, there is a library, 'syz' (Scrap Your Zippers), which provides a generic zipper for any data type, even mutually-recursive types:

http://hackage.haskell.org/packages/archive/syz/0.2.0.0/doc/...

Its internals are pretty interesting if you've ever thought about implementing a generic zipper structure. For example it uses Typeable to reify the focus type.

I'm finishing up my own generic zipper library which I hope will be simpler and more useful than syz.

jwr• 16 years ago

Clojure also has a pretty neat zipper library in contrib. I've used it in projects and I wish I had introductory material as great as this tutorial back then.

grogers• 16 years ago

Another good introduction to zippers that helped me understand them in plain terms is: http://blog.ezyang.com/2010/04/you-could-have-invented-zippe...

eru6• 16 years ago

And for those who like their math hard to understand (and rigorous): "The Derivative of a Regular Type is its Type of One-Hole Contexts" (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.8...)

It's cited as "Conor's paper" in your article. But the link there doesn't work.

eru6• 16 years ago

Here's a challenge: Design a zipper that works for cyclic graphs. There will be 10 GBP for the winner's charity of choice. (jacquesm may give another 10 Euro in addition.)

(Hint: "Purely Functional Datastructures" solves this problem for graphs shaped like a sigle ring. Perhaps this solution can be generalized?)

eru6• 16 years ago

Please post entries either to HN or send me an email. My address is in my profile.

I can also give more details about rules and conditions, if needed.

P.S. Might as well make it 100 GBP for the first challenge. I am really interested to see whether there's a solution that does it in O(1), like zippers do. (Or alternatively a proof that O(1) to move from node to node is not possible.)

copper2• 16 years ago

Wouldn't the Data.Graph.Inductive representation of a graph satisfy this (It might not be O(1), but it's pretty close)? I must admit that I find it hard to see what a zipper for a graph should look like, though.

jewbacca• 16 years ago

I've had an investigation on the backburner for a while on whether there's a zipper-like structure for representing 2D grids (eg, a game board). I feel like this may be a blind alley, because a grid would have cycles and no inherent ordering. Can anybody shed some light on this?

maxtilford• 16 years ago

I think this blog post will be relevant: http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-...

eru6• 16 years ago

Look into Okasaki's "Purely Functional Datastructures" for an example on how to handle cycles. He talks about double ended queues, which can obviously interpreted as a graph with a single cycle.

Learn you a Haskell: Zippers

Related Stories