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

What's policy around typeclass instances for std lib collection classes? #277

Closed
benhutchison opened this Issue Apr 11, 2015 · 5 comments

Comments

Projects
None yet
3 participants
@benhutchison
Copy link
Member

benhutchison commented Apr 11, 2015

More a question, but seems too involved to ask on Gitter: what's the policy & thinking around what stdlib collections have typeclass instances provided? (ie in cats.std)

  1. In scalaz, instances seem to be provided for List and Vector seqs. But I found it difficult to discover much discussion of why this choice was made, and some of the reasoning I did find (IndexedSeq vs Vector) didn't come across especially compelling to me. For cats, it would be desirable to explain the thinking behind the design.
  2. When I work with scalaz, I miss Foldable/Functor support for Iterable[T] most often when working with Map.values. I often use scala Maps as sets with fast lookup by primary key, so I end up folding/mapping over the values. In scalaz, Im forced to choose between (a) wastefully copying the Map contents into a List, or (b) defining my own Iterable instances.
  3. Ive heard at times that instances for Iterable will clash with instances of subtypes like List & Vector. However, experimentally I haven't yet observed that to happen. They seem to coexist ok in the limited cases Ive tried, the more precise instances (ie of the subtype) seem preferred by implicit resolution.
  4. Some people (eg scientific computing) need to work with number arrays (likely Array[Double]). Seems like many useful typeclasses can be defined for arrays?
@tpolecat

This comment has been minimized.

Copy link
Member

tpolecat commented Apr 12, 2015

The big problem is that it tends to be impossible to define lawful typeclass instances for mutable structures because reference identity matters. For instance, Functor[Array] isn't lawful because you can't freely exchange arr and arr.map(identity) without [potentially] changing the meaning of your program. Same applies to Seq and Iterable because you must assume in general that they are mutable.

Such instances exist in scalaz-outlaws and could exist in stray-cats, but they can't reasonably be part of cats proper.

@benhutchison

This comment has been minimized.

Copy link
Member

benhutchison commented Apr 12, 2015

Ok, thanks for explanation. Further questions:

  • "Seq and Iterable because you must assume in general that they are mutable." Slightly confused - there are immutable.Iterable and immutable.Seq that both guarantee immutability, right? However, WRT my earlier-cited use case immutable.Map#values: Iterable, that Iterable is the generic form, so maybe that's what you meant?
  • Where is stray cats? I cant find it. Just an idea ATM?
  • I envisage wanting to declare a java array as (henceforth) immutable. Arrays have unique properties and don't come in a "natively" immutable version. Might be achieved perhaps by wrapping, or type-tagging, or a read-only structural type signature.

To me , the important thing is declared intent as advised by its' type: if there's a type that says "immutable array", its safe to proceed on the basis that it is. Even "immutable" Vectors are made of mutable arrays on the inside; security policy permitting, if we really want to, we can write some reflective code that reaches into a Vector's private data and mutates it.

@tpolecat

This comment has been minimized.

Copy link
Member

tpolecat commented Apr 12, 2015

Hi, further potential answers:

  • Even if you stick with collection.immutable you find that implementations are very unconstrained; some may obey a given typeclass's laws and others may not. For instance you could define Functor[immutable.Iterable], but it wouldn't be lawful for Set or Map. I think this is a general problem with defining instances for non-final data types. Now, you might want to argue that any sensible immutable.Iterable/Seq will end up being an okay Foldable since this typeclass has very weak constraints. I'm probably not willing to go this far but others might be.
  • Stray cats was just an idea; I don't know if there has been any work on it yet.
  • I think immutable array ends up being kind of a weird data type ... scalaz has one but I don't get the sense that anyone uses it much. Maybe think more about the specific operations you would want and open another issue?

@non non added question meta labels May 22, 2015

@benhutchison

This comment has been minimized.

Copy link
Member

benhutchison commented Jul 20, 2015

https://github.com/non/alleycats closes this, I think.

@non

This comment has been minimized.

Copy link
Member

non commented Jul 20, 2015

You're right, thanks! For the specific needs you cite feel free to open issues or PRs over there.

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