New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Consider "pure profunctor" lenses #26

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

Comments

Projects
None yet
5 participants
@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

This comment has been minimized.

Show comment
Hide comment
@jdegoes

jdegoes Sep 4, 2015

Member

👍

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

Member

jdegoes commented Sep 4, 2015

👍

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

@paf31

This comment has been minimized.

Show comment
Hide comment
@paf31

paf31 Sep 4, 2015

Member

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.

Member

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

This comment has been minimized.

Show comment
Hide comment
@paf31

paf31 Sep 4, 2015

Member

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!

Member

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

This comment has been minimized.

Show comment
Hide comment
@ekmett

ekmett 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 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

This comment has been minimized.

Show comment
Hide comment
@ekmett

ekmett Sep 4, 2015

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

ekmett commented Sep 4, 2015

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

@paf31

This comment has been minimized.

Show comment
Hide comment
@paf31

paf31 Sep 6, 2015

Member

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.

Member

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

This comment has been minimized.

Show comment
Hide comment
@joneshf

joneshf Sep 6, 2015

Member

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.

Member

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

This comment has been minimized.

Show comment
Hide comment
@paf31

paf31 Sep 12, 2015

Member

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

Member

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

This comment has been minimized.

Show comment
Hide comment
@ekmett

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

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

This comment has been minimized.

Show comment
Hide comment
@puffnfresh

puffnfresh Sep 17, 2015

Member

Ah, this is great 👍

Member

puffnfresh commented Sep 17, 2015

Ah, this is great 👍

@paf31

This comment has been minimized.

Show comment
Hide comment
@paf31

paf31 Sep 19, 2015

Member

@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

Member

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

This comment has been minimized.

Show comment
Hide comment
@ekmett

ekmett Sep 19, 2015

Sadly it doesn't help.

ekmett commented Sep 19, 2015

Sadly it doesn't help.

@paf31

This comment has been minimized.

Show comment
Hide comment
@paf31

paf31 Sep 19, 2015

Member

What sort of type equalities are needed?

Member

paf31 commented Sep 19, 2015

What sort of type equalities are needed?

@ekmett

This comment has been minimized.

Show comment
Hide comment
@ekmett

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

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

This comment has been minimized.

Show comment
Hide comment
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment