Re:Learn you a Haskell: Zippers
by jberryman on Wednesday November 03, 2010 @03:32PM
(#1866138)
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:
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.
Re:Learn you a Haskell: Zippers
by eru on Wednesday November 03, 2010 @04:54PM
(#1866480)
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?)
Re:Learn you a Haskell: Zippers
by eru on Wednesday November 03, 2010 @09:39PM
(#1867241)
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.)
Re:Learn you a Haskell: Zippers
by copper on Thursday November 04, 2010 @12:05AM
(#1867629)
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.
Re:Learn you a Haskell: Zippers
by eru on Thursday November 04, 2010 @07:17AM
(#1868415)
I know how to get a zipper for a static graph by Tying the Knot (http://haskell.org/haskellwiki/Tying_the_Knot). But writing one where you can add and remove nodes and edges seems much harder.
You already know how a zipper for a tree looks like. And you have probably seen a functional queue. Generalizing from both of those, you can imagine how a zipper would work.
I can write down the types and all, even if I don't know of any implementation. But that's probably a topic for a blog post, or so.
Re:Learn you a Haskell: Zippers
by jwr on Wednesday November 03, 2010 @03:40PM
(#1866170)
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.
Re:Learn you a Haskell: Zippers
by jewbacca on Wednesday November 03, 2010 @06:25PM
(#1866784)
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?
Re:Learn you a Haskell: Zippers
by eru on Wednesday November 03, 2010 @10:07PM
(#1867319)
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.
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.
(Hint: "Purely Functional Datastructures" solves this problem for graphs shaped like a sigle ring. Perhaps this solution can be generalized?)
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.)
You already know how a zipper for a tree looks like. And you have probably seen a functional queue. Generalizing from both of those, you can imagine how a zipper would work.
I can write down the types and all, even if I don't know of any implementation. But that's probably a topic for a blog post, or so.
The types I was talking about go as: type Context a b = (Adj b, Node, a, Adj b) type Adj b = [(b, Node)]
It definitely allows traversal, and adding nodes seems to be possible, too (judging from the api, of course, it ought to be :)
It's cited as "Conor's paper" in your article. But the link there doesn't work.