search

typelevel / algebra

Experimental project to lay out basic algebra type classes
https://typelevel.org/algebra/
Other
378 stars 69 forks source link

Add combinators to transform type of Ring, Group, Eq, etc #116

Closed tixxit closed 7 years ago

tixxit commented 8 years ago

For types like Ring, we should include an imap(f: A => B, g: B => A): Ring[B] method for transforming the type class. This also include contramap(f: B => A) on type classes like Eq and Order.

johnynek commented 8 years ago

Sounds like we need a Bijection. :) We added something like this to Bijection actually: https://github.com/twitter/bijection/pull/183/files which let's you generalize this imap idea.

Also, it algebird we added bijected algebras: https://github.com/twitter/algebird/blob/develop/algebird-bijection/src/main/scala/com/twitter/algebird/bijection/AlgebirdBijections.scala#L31

Here, Eq.on is the same as contramap. As is Order.on.

About imap, see #108. That one, which I think should probably rarely be used (at Twitter, bijected algebras are pretty rare actually. One benefit of the bijected algebra is that you can leverage combineAll to not apply the bijection too much, but the naive approach of applying both functions on each combine to combine a big list is costly).

I'd probably not add imap, and instead make a class similar to BijectedRing to handle this.

non commented 8 years ago

In Cats I originally had a bijection type but realized I didn't want to step on twitter/bijection's toes, so we removed it. I agree that it's a lot cleaner.

I think the "bijected algebra" (or "mapped algebra") approach makes a lot of sense for the reasons you mention. I could imagine a similar argument being used in favor of putting concrete sorting implementations on Order so it could be more efficient in these cases as well, but I'm not sure that would be the right decision, since there are so many other methods you might want too (sorting, selecting, searching, etc).

TomasMikula commented 8 years ago

It could also be

contramap[A, B](ra: Ring[A])(f: Iso[B, A]): Ring[B]

but I guess folks don't want to pull in a lens library.

EDIT: I corrected Lens to Iso.

tixxit commented 8 years ago

@johnynek Ah - that looks delightful. If we had these methods existing on the type classes already, then it would make the implementation of a TypeclassBijection easier, right? The bijection style looks nice, but it doesn't preclude us from having some combinators on the type classes to start? As you noted, they already exist for Eq and Order.