Skip to content
This repository has been archived by the owner. It is now read-only.

Consider "pure profunctor" lenses #26

Closed
ekmett opened this issue Sep 4, 2015 · 15 comments
Closed

Consider "pure profunctor" lenses #26

ekmett opened this issue Sep 4, 2015 · 15 comments

Comments

@ekmett
Copy link

@ekmett ekmett commented Sep 4, 2015

In the lens library in Haskell we're encumbered by trying to interoperate with base and with a historical codebase. One sign of that is our representation for lenses is

type Lens s t a b = forall f. Functor f => (a -> f b) -> s -> f t

which is the "van Laarhoven" representation, so that it can compose directly with the function traverse and folks can define lenses without incurring a dependency on the package at all.

On the other hand, a formulation of lenses based on just profunctors:

type Iso s t a b = forall p. Profunctor p => p a b -> p s t
type Lens s t a b = forall p. Strong p => p a b -> p s t
type Prism s t a b = forall p. Choice p => p a b -> p s t

has a large number of theoretical advantages.

Notably:

  • The from combinator that reverses an Iso can reverse a Prism, and you can then just get from it as normal rather than having to have re as a special case. from also becomes capable of "turning a lens around" in a meaningful way. With the addition of Costrong and Cochoice classes you can reverse them again and get back a Prism correctly rather than a mere view.
  • There are fewer type parameters floating around for users to get wrong.
  • This generalizes to other monoidal categories. Under a sufficiently general viewpoint/implementation you can see prisms as lenses into a different monoidal category obtained by looking at Hask with Either as a monoidal category rather than Hask with (,) as a monoidal category. Down that road Strong and Choice collapse into one class, but you need more scaffolding to support it all.

Downsides:

  • You need a story for Traversals, one is to say p is a representable profunctor represented by a applicative functor. This is sufficient to be a legal encoding but isn't terribly satisfying.
  • This doesn't yet give a story for indexed traversals or indexed lenses.

I figured I'd mention it here because you don't have my legacy support issues, or quite the same number of dependencies that cause folks to view lens as a painful import to make the same trade-offs I made necessarily make sense for you.

@jdegoes
Copy link
Contributor

@jdegoes jdegoes commented Sep 4, 2015

👍

Also, @ekmett, welcome to the PureScript community. 😄

@paf31
Copy link
Contributor

@paf31 paf31 commented Sep 4, 2015

Very interesting. I lack the sufficient lens-fu to comment meaningfully on this yet, but it seems conceptually simpler, which I like. Regarding indexed traversals, are there any possible solutions on the horizon? I ask because optic-ui would probably make use of them, if they existed in purescript-lens.

Also, I'm not sure if you've seen purescript-optic, but that has more of the Traversal machinery, as well as Iso and a few other pieces.

@paf31
Copy link
Contributor

@paf31 paf31 commented Sep 4, 2015

On the other hand, optic-ui would almost certainly benefit from the pure profunctor approach, since its UI is almost certainly a Profunctor, so it would get various combinators "for free" this way.

And to echo @jdegoes, welcome!

@ekmett
Copy link
Author

@ekmett ekmett commented Sep 4, 2015

The problem from the standpoint of indexed traversals is that when I use p a (f b) -> s -> f t as an indexed optic, then when I compose them with (.) then unification forces p to be (->) the outer traversal so you only get the inner traversal's index.

On the other hand, here we only have one parameter p, not two like the p and f so I can't use unification to force things to behave that way and typeclasses aren't smart enough to figure out what to do.

@ekmett
Copy link
Author

@ekmett ekmett commented Sep 4, 2015

The nice thing about this form of Iso is that iso is just dimap.

@paf31
Copy link
Contributor

@paf31 paf31 commented Sep 6, 2015

I put this together as a starting point, but as the gif indicates, I really could use some help.

https://github.com/paf31/purescript-profunctor-lenses/tree/master

In particular, I'm not sure if the Traversal approach is sound.

@joneshf
Copy link
Contributor

@joneshf joneshf commented Sep 6, 2015

Very cool idea.

My only concern is, what does this change for the end user? If someone wants to define a lens, do they have to depend on profunctor now in order to do that? Or can they still define their lenses without an explicit dependency?

Also, the indexed stuff isn't really a concern with this idea since we can't implement those ideas well enough as it stands now. At least, not using type classes. The Representable family falls apart after a while, so we'd have to think up Indexable from a different approach anyway.

@paf31
Copy link
Contributor

@paf31 paf31 commented Sep 12, 2015

Perhaps @zrho's Wander representation in profunctor-lenses is a way to get indexed traversals?

profunctor-lenses is now up-to-date with lens and optics thanks to @zrho's latest PR. We might want to consider whether we want to merge back to lens. I'm totally fine maintaining profunctor-lenses as a separate repo if you'd rather not though.

For me, the application to optic-ui is enough reason to prefer profunctor-lenses for the particular use case where you have a Profunctor already and want composition operators "for free", but I think both have their use cases (purescript-lens is very good as a lightweight lens implementation, for example, with optics if a user needs the heavier machinery).

@ekmett
Copy link
Author

@ekmett ekmett commented Sep 12, 2015

You can't really get indexed traversals without introducing without some notion of type equalities. You want (->) work work as an instance of the indexed abstraction for any index, but Indexed i to only work for i, so even MPTCS + FDs isn't enough.

@puffnfresh
Copy link

@puffnfresh puffnfresh commented Sep 17, 2015

Ah, this is great 👍

@paf31
Copy link
Contributor

@paf31 paf31 commented Sep 19, 2015

@ekmett I'm not sure I fully understand the need for type equalities, but would something like this help?

https://github.com/paf31/purescript-leibniz/blob/master/docs/Data/Leibniz.md

@ekmett
Copy link
Author

@ekmett ekmett commented Sep 19, 2015

Sadly it doesn't help.

@paf31
Copy link
Contributor

@paf31 paf31 commented Sep 19, 2015

What sort of type equalities are needed?

@ekmett
Copy link
Author

@ekmett ekmett commented Sep 19, 2015

In the normal encoding of lens I use something like:

class Profunctor p => Indexable i p where
  indexed:: p a b -> i -> a -> b

instance Indexable i (->) where
  indexed = const

newtype Indexed i a b = Indexed { runIndexed :: i -> a -> b }

instance (i ~ j) => Indexable i (Indexed j) where
  indexed = runIndexed

Notice how once we know we're interested in the Indexed case that we gain information that i is j, but that the (->) case works with all choices of i.

Now you can use this inside of an optic.

type IndexedTraversal i s t a b = forall p f. (Indexable i p, Applicative f) => p a (f b) -> s -> f t

The issue is we need to gain information about type equality as we walk up to the superclass in the Indexed case.

@joneshf
Copy link
Contributor

@joneshf joneshf commented Apr 21, 2016

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
5 participants
You can’t perform that action at this time.