Learn you a Haskell: Zippers • Hacker News Board

Re: Learn you a Haskell: Zippers

#11

Post by copper » Thu, Nov 04, 2010, 4:05 AM UTC

eru wrote: post #9

eru wrote: post #6

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

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

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

#12

Post by eru » Thu, Nov 04, 2010, 11:17 AM UTC

copper wrote: post #11

eru wrote: post #9

Earlier quoted context omitted.

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

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.

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

#13

Post by copper » Thu, Nov 04, 2010, 12:42 PM UTC

eru wrote: post #12

copper wrote: post #11

Earlier quoted context omitted.

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.

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…

I think I understand that, but without actually writing it out, it's going to be impossible to test.

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

Re: Learn you a Haskell: Zippers

#14

Post by eru » Thu, Nov 04, 2010, 3:12 PM UTC

copper wrote: post #13

eru wrote: post #12

Earlier quoted context omitted.

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…

I think I understand that, but without actually writing it out, it's going to be impossible to test. 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 :)

From the types you give, I can't see how it works. Would you please elaborate?