Re: [Haskell] An Alternative Data.List.Zipper
On Sat, 2009-01-17 at 21:55 +0100, Jean-Philippe Bernardy wrote:
I think it should admit empty, and the traversable instance should traverse the first list in reverse.
I fixed the latter issue so that the behavior is correct (I think). I tested it like this:
forM (next $ next $ fromList [1..5]) $ \i -> do { print i; return i } 1 2 3 4 5 [1,2] 3 [4,5]
which I believe is proper. I'm undecided about allowing them to be empty. I don't know the theory or math behind zippers (I'm sure there are some papers written about it), but it doesn't make much sense to be empty. I got that impression from #haskell, also. Thanks for the comments. :) Jeff Wheeler
On Sat, Jan 17, 2009 at 4:32 PM, Jeff Wheeler <jeff@nokrev.com> wrote:
On Sat, 2009-01-17 at 21:55 +0100, Jean-Philippe Bernardy wrote:
I think it should admit empty, and the traversable instance should traverse the first list in reverse.
I fixed the latter issue so that the behavior is correct (I think).
That's correct, but I think you'd be better off defining OpApplicative (or Backward, as I call it) locally and avoiding the two reverses.
I'm undecided about allowing them to be empty. I don't know the theory or math behind zippers (I'm sure there are some papers written about it), but it doesn't make much sense to be empty. I got that impression from #haskell, also.
If you look at a zipper as a list with a selected element, then it doesn't make sense to talk about a zipper of an empty list. That being said, I'd prefer fromList to have the type [a] -> Maybe (Zipper a), and similarly with next and previous. If people want to live dangerously, they can use fromJust. -- Dave Menendez <dave@zednenem.com> <http://www.eyrie.org/~zednenem/>
On Sat, 2009-01-17 at 17:41 -0500, David Menendez wrote:
That's correct, but I think you'd be better off defining OpApplicative (or Backward, as I call it) locally and avoiding the two reverses.
I'll have to look into this more; I don't really understand applicatives right now, so I can't use them yet. :)
If you look at a zipper as a list with a selected element, then it doesn't make sense to talk about a zipper of an empty list.
Apparently a zipper can be empty, as the focus is the rest of the list, not the current element. It seems that my file is not a Zipper, but rather a PointedList (thanks to roconner in #haskell). Therefore, I've changed my file to use the new name throughout, including a new module name. With this change, I think it's now appropriate to post on Hackage.
That being said, I'd prefer fromList to have the type [a] -> Maybe (Zipper a), and similarly with next and previous. If people want to live dangerously, they can use fromJust.
I agree, and I've made this change. I found this annoying on next/previous though, so I've created a tryNext/tryPrevious that'll return an unchanged PointedList if it's already on the end. Here's the new version: http://hpaste.org/14030#a5 Thanks for the feedback, Jeff Wheeler
On Sat, Jan 17, 2009 at 7:49 PM, Jeff Wheeler <jeff@nokrev.com> wrote:
On Sat, 2009-01-17 at 17:41 -0500, David Menendez wrote:
That's correct, but I think you'd be better off defining OpApplicative (or Backward, as I call it) locally and avoiding the two reverses.
I'll have to look into this more; I don't really understand applicatives right now, so I can't use them yet. :)
newtype Backwards f a = B { unB :: f a } instance Functor f => Functor (Backwards f) where fmap f = B . fmap f . unB instance Applicative f => Applicative (Backwards f) where pure = B . pure f <*> x = B (unB f <**> unB x) traverseBackwards :: (Traversable t, Applicative f) = (a -> f b) -> t a -> t (f b) traverseBackwards f = unB . traverse (B . f)
If you look at a zipper as a list with a selected element, then it doesn't make sense to talk about a zipper of an empty list.
Apparently a zipper can be empty, as the focus is the rest of the list, not the current element. It seems that my file is not a Zipper, but rather a PointedList (thanks to roconner in #haskell).
This may be terminological confusion. I would have said that a PointedList *is* a zipper. Certainly, from the standpoint that zippers are comonads, you can't have an empty zipper, because you always need to be able to retrieve the selected value.
That being said, I'd prefer fromList to have the type [a] -> Maybe (Zipper a), and similarly with next and previous. If people want to live dangerously, they can use fromJust.
I agree, and I've made this change. I found this annoying on next/previous though, so I've created a tryNext/tryPrevious that'll return an unchanged PointedList if it's already on the end.
I would define tryNext in terms of next, rather than the other way around, but I guess it shouldn't make much difference. I'm also not sure that returning the original pointed list is a good idea, since trying to move beyond the boundaries of the zipper will usually be an error. -- Dave Menendez <dave@zednenem.com> <http://www.eyrie.org/~zednenem/>
On Sat, 17 Jan 2009, David Menendez wrote:
instance Applicative f => Applicative (Backwards f) where pure = B . pure f <*> x = B (unB f <**> unB x)
probably should be f <*> x = B (unB x <**> unB f) anyhow, this should be part of Control.Applicative.
This may be terminological confusion. I would have said that a PointedList *is* a zipper.
This is what I thought, and what how I initally advised Jeff. However after carefully reading both <http://en.wikibooks.org/wiki/Haskell/Zippers> and <http://www.cs.nott.ac.uk/~ctm/Dissect.pdf> (Clowns to the left of me, jokers to the right), it is clear that formally a zipper focuses on a sub-list / sub-tree rather than focusing on a particular node of a list or a tree. Hence zippers are not comonads. -- Russell O'Connor <http://r6.ca/> ``All talk about `theft,''' the general counsel of the American Graphophone Company wrote, ``is the merest claptrap, for there exists no property in ideas musical, literary or artistic, except as defined by statute.''
On Sat, Jan 17, 2009 at 9:13 PM, <roconnor@theorem.ca> wrote:
On Sat, 17 Jan 2009, David Menendez wrote:
instance Applicative f => Applicative (Backwards f) where pure = B . pure f <*> x = B (unB f <**> unB x)
probably should be f <*> x = B (unB x <**> unB f)
I always get that backwards.
anyhow, this should be part of Control.Applicative.
I agree. But until it is, we'll have to make do.
This may be terminological confusion. I would have said that a PointedList *is* a zipper.
This is what I thought, and what how I initally advised Jeff. However after carefully reading both <http://en.wikibooks.org/wiki/Haskell/Zippers> and <http://www.cs.nott.ac.uk/~ctm/Dissect.pdf> (Clowns to the left of me, jokers to the right), it is clear that formally a zipper focuses on a sub-list / sub-tree rather than focusing on a particular node of a list or a tree. Hence zippers are not comonads.
Funny, I was just reading that paper earlier today. You're right. I wasn't making enough of a distinction between zippers and structures with one selected element. It's the latter which are comonads. -- Dave Menendez <dave@zednenem.com> <http://www.eyrie.org/~zednenem/>
participants (3)
-
David Menendez -
Jeff Wheeler -
roconnor＠theorem.ca