Split {Functor,Foldable,Traversable}WithIndex to a separate package

[arybczak]

Mirror for well-typed/optics#309

optics also defines these classes and it would be good to not duplicate them.

Also, if it was a standalone package, people could use it without depending on either lens or optics.

[RyanGlScott]

I'm unclear on what the relationship between the existing keys library and what you're looking for would be. If we do split out the *WithIndex classes, I'd like there to be some kind of story about classifying the purposes of these various libraries that provide keyed/indexed abstractions.

[phadej]

keys description:

In practice this package is largely subsumed by the lens package, but it is maintained for now as it has much simpler dependencies.

---

keys is TypeFamilies and *WithIndex classes are FunctionalDependencies based.

---

keys has ZipWithKey class, but I use https://hackage.haskell.org/package/semialign-indexed-1.1/docs/Data-Semialign-Indexed.html nowadays (and there is a sibling packages defining classes on top of optics versions).

I'd be very happy to make semialign-indexed depend on something shared by lens and optics.

---

keys also has FoldableWithKey1 and TraversableWithKey1, but there are no analogous classes in lens or optics, so I'd say they could just be dropped. Foldable1 doesn't seem to take off.

---

lens variants have lens specific (conjoined) method. As there is no "proof" whether that is strictly needed and it does ties to make optimized do something which it might just decide to not do, I don't think they are important.

I guess @ekmett my disagree (but I'd leave the proof obligation on him, or whoever objects) to show they are strictly required, and optimizer cannot be made to do the right thing otherwise.

---

TL;DR keys vs new-package is type families or functional dependencies question.

---

The benefit of FD, is e.g. Each in optics. It is cleaner to add i with FDs, then have a type-family EachIndex or EachKey.

[RyanGlScott]

TL;DR keys vs new-package is type families or functional dependencies question.

I see.

lens variants have lens specific (conjoined) method. As there is no "proof" whether that is strictly needed and it does ties to make optimized do something which it might just decide to not do, I don't think they are important.

Yes, this is definitely an awkward sticking point. I suspect that if you tried factoring out everything that conjoined uses into its own package, you'd end up needing a surprising amount of machinery from lens. I'm unclear on what the consequences of removing the lens-specific methods from the *WithIndex classes would be.

[arybczak]

TraversableWithIndex as itraversed, FoldableWithIndex has ifolded and FunctorWithIndex has imapped as a member, but their default implementations are never redefined (apart from itraversed being defined as traversed for [], ZipList and vector, though default itraversed uses itraverse, which then calls traversed, so that redefinition seems redundant).

FWIW optics doesn't define these as members and benchmarks comparing performance of itraversed etc. with lens show that there is no penalty for that.

[ekmett]

I don’t know what you mean by there being no proof that the conjoined machinery is necessary. When we finally gave in and added it, it made quite an observable performance difference over the naive encoding. If you think about it for non-trivial indexes the difference is between doing that work at all or being able to completely skip it. Bikeshedding to remove them seems to need to meet a pretty high proof bar to me; to me the proof burden is the other way around at this point, as without it you are now relying on worker-wrapper, a metric boatload of inlining and optimizations that at last check GHC was incapable of doing to remove significant costs or forcing users to make duplicate names for the indexed and non-indexed versions, which is actively against the design philosophy of lens.

…

-Edward

On Sep 28, 2020, at 6:44 AM, Oleg Grenrus ***@***.***> wrote:  keys description: In practice this package is largely subsumed by the lens package, but it is maintained for now as it has much simpler dependencies. keys is TypeFamilies and *WithIndex classes are FunctionalDependencies based. keys has ZipWithKey class, but I use https://hackage.haskell.org/package/semialign-indexed-1.1/docs/Data-Semialign-Indexed.html nowadays (and there is a sibling packages defining classes on top of optics versions). I'd be very happy to make semialign-indexed depend on something shared by lens and optics. keys also has FoldableWithKey1 and TraversableWithKey1, but there are no analogous classes in lens or optics, so I'd say they could just be dropped. Foldable1 doesn't seem to take off. lens variants have lens specific (conjoined) method. As there is no "proof" whether that is strictly needed and it does ties to make optimized do something which it might just decide to not do, I don't think they are important. I guess @ekmett my disagree (but I'd leave the proof obligation on him, or whoever objects) to show they are strictly required, and optimizer cannot be made to do the right thing otherwise. TL;DR keys vs new-package is type families or functional dependencies question. The benefit of FD, is e.g. Each in optics. It is cleaner to add i with FDs, then have a type-family EachIndex or EachKey. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or unsubscribe.

[arybczak]

I don’t know what you mean by there being no proof that the conjoined machinery is necessary

Ah, but we're not saying that (indeed, conjoined is quite nice).

It's about having itraversed/ifolded/imapped as standalone functions instead of class members.

[ekmett]

I don’t have a strong objection to that part, at least off the cuff. I don’t recall a performance motivation for folding then into the class, mostly convenience about which gets defined, though I could be wrong. It has been several years. I presume moving them to top level definitions or definitions per package that needs a different presentation would make it easier for, say, optics to roll its own flavor of them then? I have a mild dislike for the fact that you are going to have a hard time convincing folks to flip their dependencies in my experience, and so it’d force lens into the -extras orphan instance pattern that I rather assiduously avoid. I’m happy to consider grossly deprecating all of keys except for this part of the API and translocating these classes these wholesale with the tweak. I’d also consider a fresh package as a destination rather than deal with causing existing users of the long deprecated-in-my-mind keys package undue pain. The major source of disquiet for me again is that getting stuck with a package full of orphans really sticks in my craw.

…

On Oct 4, 2020, at 8:24 PM, Andrzej Rybczak ***@***.***> wrote:  I don’t know what you mean by there being no proof that the conjoined machinery is necessary Ah, but we're not saying that (indeed, conjoined is quite nice). It's about having itraversed/ifolded/imapped as standalone functions instead of class members. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or unsubscribe.

[phadej]

I presume moving them to top level definitions or definitions per package that needs a different presentation would make it easier for, say, optics to roll its own flavor of them then?

optics does roll own flavor on top of general FunctorWithIndex ...

This issue is a motivation to having just single FunctorWithIndex which would make it easier to folks to define it, than to depend on both lens and optics to define it. (Though, for Ix and At that still will be the case, have to start somewhere).

I’m happy to consider grossly deprecating all of keys except for this part of the API and translocating these classes these wholesale with the tweak. I’d also consider a fresh package as a destination rather than deal with causing existing users of the long deprecated-in-my-mind keys package undue pain.

I'm in favor of new package, say indexes.

Control.Lens.Indexed imports modules from array, (formerly) transformers, unordered-containers and vector. It's another small hill, but I do think that unordered-containers and vector maintainers could be persuaded to flip the dependency in the long term. indexes can IMO depend on all of these in the beginning. (This will cause problem to dependency-super-minimality of optics-core, but if that's the case, then we have a stalemate situation).

I don't think anything else have to be flipped, people who define FunctorWithIndex.. now by importing Control.Lens could still continue doing that, if lens decides to re-export them.

In other words, I don't see a need for a "package full of orphans".

[RyanGlScott]

This was done in #947 and #951.