Re: [Haskell] An Alternative Data.List.Zipper

[David Menendez]

On Sat, Jan 17, 2009 at 9:13 PM,   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  and
>  (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 

___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell

Re: [Haskell] An Alternative Data.List.Zipper

[roconnor]

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 
 and 
 (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  
``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.''
___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell

Re: [Haskell] An Alternative Data.List.Zipper

[David Menendez]

On Sat, Jan 17, 2009 at 7:49 PM, Jeff Wheeler  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 

___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell

Re: [Haskell] An Alternative Data.List.Zipper

[Jeff Wheeler]

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

___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell

Re: [Haskell] An Alternative Data.List.Zipper

[David Menendez]

On Sat, Jan 17, 2009 at 4:32 PM, Jeff Wheeler  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 

___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell

Re: [Haskell] An Alternative Data.List.Zipper

[Jeff Wheeler]

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

___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell

Re: [Haskell] An Alternative Data.List.Zipper

[Jeff Wheeler]

On Sat, 2009-01-17 at 10:44 -0800, Max Rabkin wrote:

> This traverses the list three times (reverse, init and last are each
> linear time):
> fromListEnd xs = Zipper (reverse $ init xs) (last xs) []
> 
> But we only need to do it once:
> fromListEnd xs = let x:xs' = reverse xs in Zipper xs' x []
> 
> I don't *think* this has an effect on strictness/laziness, since both
> versions are strict in the spine of the list.

Excellent suggestion; your solution is much more readable and faster.

I've made the change here: http://hpaste.org/14030#a1

Thanks,

Jeff Wheeler

___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell

Re: [Haskell] An Alternative Data.List.Zipper

[Max Rabkin]

This traverses the list three times (reverse, init and last are each
linear time):
fromListEnd xs = Zipper (reverse $ init xs) (last xs) []

But we only need to do it once:
fromListEnd xs = let x:xs' = reverse xs in Zipper xs' x []

I don't *think* this has an effect on strictness/laziness, since both
versions are strict in the spine of the list.

--Max

On Sat, Jan 17, 2009 at 10:33 AM, Jeff Wheeler  wrote:
> Hi,
>
> (I also sent this to libraries@, but without response; I'm posting here
> for a wider audience.)
>
> I'm somewhat of a beginner in Haskell, so take what I say with a grain
> of salt, please.
>
> The ListZipper implementation seems very odd to me, and #haskell seemed
> to agree with me. The current package implements a Zipper with
>
>> data Zipper = Zipper ![a] ![a]
>
> which allows for empty zippers, among other things. Very strange to me.
> It also seems unnecessarily strict. There are also no expected
> typeclasses implemented, like Foldable or Traversable.
>
> I thought it would be interesting to try fixing these problems with a
> much cleaner design, and I'd like to share what I came up with:
>
> http://hpaste.org/14030
>
> I'd very much appreciate some criticism of the code so that I can
> improve it.
>
> I'm not sure how best to provide this alternative on Hackage; should we
> make this merely a newer version of the old library, provide it in a
> conflicting package, or find a new namespace for it and provide it
> there?
>
> Thanks,
>
> Jeff Wheeler
>
> ___
> Haskell mailing list
> Haskell@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell
>
___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell