search

ekmett / lens

Lenses, Folds, and Traversals - Join us on web.libera.chat #haskell-lens
http://lens.github.io/
Other
2k stars 269 forks source link

Add some kind of lens based zipper? #50

Closed ekmett closed 11 years ago

ekmett commented 11 years ago

I've been considering adding a zipper module for some time. I hacked up @jberryman's zippo library to use lens.

Issues:

Where to put it?

If it lived in Control.Lens.Zipper it would be odd if it wasn't exported from Control.Lens, (since I do re-export Control.Lens.* for everything except Control.Lens.Internal, but if it was exported from Control.Lens it would take a lot of useful names that I've deliberately avoided touching because they are popular in end user code.

ekmett commented 11 years ago

I took the code in a rather different direction than, zippo, or rather in a more extreme notational direction.

A Zipper in lens looks like

myZipper :: Top :> Foo :> Bar :> Baz

The only use of the Zipper name is for the class used to package back up the re-zipped value in the end.

jberryman commented 11 years ago

While others sleep, you code :) This is great, and I'm looking forward to studying the final implementation you release. I've always thought a lens-based zipper was a great motivating higher-order use of lenses, and useful for guiding lens lib. design and justifying the claim that they're an abstraction that should be embraced more fully; though I'm skeptical of the need for zippers, beyond a few very specific applications like xmonad.

IYI here are the areas I was planning on focusing on (and might still execute on) in zippo in the near future:

  1. performance: through simplicity of implementation, and clever rewrite rules, allow GHC to produce highly-optimized code

  2. define a few combinators that form a pleasant mini-eDSL for zipper operations, e.g. (.^>) :: (a -> Zipper st b) -> (b -> Zipper st b -> c) -> a -> c which allows binding to the focus, then composing additional zipper operations (better name might be \>>) as in:

    zscan a = zipper >>> moveP fstL >>> moveP fstL >>> modf (+a) .^> 
                \a-> moveUp >>> moveP sndL >>> modf (+a) .^>
                \a-> moveUp >>> moveUp >>> moveP sndL >>> moveP fstL >>> modf (+a) .^>
                \a-> moveUp >>> moveP sndL >>> modf (+a) >>> close

    I can get you the other combinators I've found useful if you're interested.

  3. try to approach some of Oleg's work including making use of the real-world XML annotation use-case, and looking at zippers w/ concurrent foci (what you've already done with Traversal is pretty cool and I suppose related).

I'd appreciate it if you'd mention my name, and reference my work on pez and zippo in the code or docs somewhere, when you end up releasing; to the best of my knowledge the lens-based zipper approach is novel (if obvious in hindsight); as I think are the level of type-safety, and support for heterogeneous motions provided by zippo (although it looks like Oleg's Scrap Your Zipper work uses a similar approach) and save/restore/etc junk in 'pez'.

Happy hacking!

ekmett commented 11 years ago

I'm currently planning to largely ignore performance issues. I don't anticipate they'll be too bad, given that it gets to ride the same performance benefits that lens provides elsewhere.

Regarding zipper operations, one of the projects I have in the work is issue #54, which is to port back the Lensed monad I helped built for snap a year or two back at Hac φ. I figure If I can port that using a Zipper rather than the single Lens like I do there, then the breadcrumb might actually be the website breadcrumb.

This would wind up being similar to your 2.) DSL, except with horizontal (type changing) motions effectively guarded by recursion.

I was planning on doing a haddock pass over the code today. Of course, I'll definitely include your name and a nod to zippo. My apologies for more or less wholesale stealing the design and running with it, but I really wanted it to be a building block for working with LensedT (which I suppose is now, probably, ZippedT)

I've had a lens based zipper in code before, but I must confess, I like the breadcrumb-like signature of your zippo model better than the version i was using. I was just capturing the types of the start and end as a thrist which meant i couldn't really do a type safe 'up' motion, but only give you an existential context when you moved up, which required you to work CPS'd.

On the other hand, the existential context trick may still prove to be valuable for 'long range' motions like you have in pez.

jberryman commented 11 years ago

All great stuff. And no apologies necessary; tis the nature of OSS, and it's nice to see the ideas validated. I just figured I'd let you know what would offend my vanity now rather than after the fact.

On Wed, Sep 19, 2012 at 12:56 PM, Edward A. Kmett notifications@github.comwrote:

I'm currently planning to largely ignore performance issues. I don't anticipate they'll be too bad, given that it gets to ride the same performance benefits that lens provides elsewhere.

Regarding zipper operations, one of the projects I have in the work is issue #54 https://github.com/ekmett/lens/issues/54, which is to port back the Lensed monad I helped built for snap a year or two back at hac phi. I figure If I can port that using a Zipper rather than the single Lens like I do there, then the breadcrumb can actually be the website breadcrumb.

This would wind up being similar to your #2https://github.com/ekmett/lens/issues/2dsl, except with horizontal (type changing) motions effectively guarded by recursion.

I was planning on doing a haddock pass over the code today. Of course, I'll definitely include your name and a nod to zippo. My apologies for more or less wholesale stealing the design and running with it, but I really wanted it to be a building block for working with LensedT (which I suppose is now, probably, ZippedT)

I've had a lens based zipper in code before, but I must confess, I like the breadcrumb-like signature of your zippo model better than the version i was using. I was just capturing the types of the start and end as a thrist which meant i couldn't really do a type safe 'up' motion, but only give you an existential context when you moved up, which required you to work CPS'd.

— Reply to this email directly or view it on GitHubhttps://github.com/ekmett/lens/issues/50#issuecomment-8697922.

ekmett commented 11 years ago

Regarding your .^> combinator, I'm definitely interested in what has worked out well for you in practice.

My first thought was that a variant that fits the stye of the other combinators in lens a little better might be

(%>) :: (a :> b) -> (b -> (a :> b) -> c) -> c

with a fixity matching %, and possibly a ^%> with a fixity matching the tighter fixity of ^%.

But, er, I guess that doesn't work:

z %> \b -> right1 %> \c -> left1 % focus .~ (b + c)

That doesn't look like it works because the associativity is wrong. and the \ captures the tail.

Perhaps I do need to add a few cps'd combinators at the infixr 1 level to match (>>>) like the one you proposed.