cats - OneAnd.scala

[Kevin Meredith]

Looking at this class's [constructor](https://github.com/non/cats/blob/master/core/src/main/scala/cats/data/OneAnd.scala#L16):

final case class OneAnd[F[_], A](head: A, tail: F[A])

It seems to me that there's no constraint on `F`.

For example, I could do:

scala> import cats.data.OneAnd

import cats.data.OneAnd

scala> import cats.data.OneAndInstances

import cats.data.OneAndInstances

scala> case class F[A](x: Int)

defined class F

scala> OneAnd[F, Int](555, F[Int](1234))

res1: cats.data.OneAnd[F,Int] = OneAnd(555,F(1234))

I faintly recall asking a similar question a while ago in a Haskell library. I think that the answer involved "constraints are not implemented at the data type

level," but that's a very weak memory.

Thanks,

Kevin

[Cody Allen]

I faintly recall asking a similar question

I'm not sure you actually asked a question here :)

You are correct that F is unconstrained when you go to create a OneAnd instance. The constraints will come in as needed on individual methods. For example, if you want to find an element, F must have a Foldable instance. If you want to filter elements, F must have a MonadCombine instance.

By enforcing these constraints on F only where they are needed, OneAnd is more flexible. If it required all of the constraints in the constructor, then it would require the union of all of the constraints of the individual methods, which would drastically reduce the number of F type constructors that could be used with OneAnd. There's no reason to require that F has a MonadCombine instance if all you want to do is find an element (which just requires a way to iterate over the elements).

Does that clear things up a bit?

[Kevin Meredith]

Thanks, Cody, for answering my implied question :).

Also, I found that StackOverflow question - http://stackoverflow.com/a/32814356/409976. I believe that the following LYAH summarizes Aadit's answer:

However, it is a very strong convention in Haskell to never add type class constraints in data declarations.

Is that convention present in `cats` too?

[Ben Hutchison]

IMO Kevin, that's an open question, a subject of some controversy.

/Typically/, data types don't need typeclass instances captured at creation time. But Im not convinced about /never/. 

One oft-debated example is a tree-based Set. If you insert elements under a given ordering, you need to look them up with the same ordering. IMO the best way to do that is to capture the ordering when the set is created, as Daniel argued here [https://github.com/scalaz/scalaz/issues/671]. As you can see on the ticket, others disagree.

The alternative option to capture-at-create-time seems to be what's been called "global uniqueness of instances" [http://blog.ezyang.com/2014/07/type-classes-confluence-coherence-global-uniqueness/]. This is the idea that typeclass bindings must exist in a global scope that cuts across all modules in a program, and there must be only one typeclass instance for given data type. 

"Anti-modular" sums up why I dislike the global instance design. Some people believe its crucial for typeclasses to work correctly, but I do wonder if they're conditioned by how haskell works.

-Ben

​

[Erik Osheim]

On Tue, Feb 02, 2016 at 11:33:04PM +1100, Ben Hutchison wrote:
> IMO Kevin, that's an open question, a subject of some controversy.

I agree. I would say that capturing type class instances is
mildly-discouraged (if nothing else it can bloat a data structure) but
not forbidden.

> "Anti-modular" sums up why I dislike the global instance design. Some
> people believe its crucial for typeclasses to work correctly, but I do
> wonder if they're conditioned by how haskell works.

An interesting point here is that even Haskell doesn't verify global
instance uniqueness -- there is just a social convention against
providing orphan type class instances which might not be unique. But
as far as I know this property is not actually checked or enforced.

Being able to define orphan instances is one of the most attractive
things about using type classes in Scala. For example, I can define a
spire.algebra.Monoid for org.joda.time.Duration without having to
patch the Spire or Joda-Time projects. So I would be very reluctant to
tell people that they should never define orphan instances in Scala.

All of this is to say that this is an open issue and I don't think
there's an answer that satisfies everyone (yet).

-- Erik

[Simon Ochsenreither]

My rule of the thumb is more or less that if an implementation requires a constraint to be able to function (no, "I can create an empty set/a single-element set without it" in the set example doesn't count) it needs to bind to the instance, otherwise it can go on the specific method (the sum method might be a good example for that).

This allows more flexible usage of different implementations, because you don't need to drag the different constraints through your code after construction of the structure.

I'd be wary to trust the conventional Haskell design approach given that type class coherence/confluence/uniqueness has been broken for more than half a decade already, with no fix in sight. (The reason why the "obvious" fix has never been implemented and people keep relying on "don't do this" is that it's completely impractical to enforce. Enforcement would require that every author of every typeclass and every author of every data declaration for every library ever invented or invented in the future would need to coordinate to provide instances.)

[Kevin Meredith]

> I'd be wary to trust the conventional Haskell design approach given that type class coherence/confluence/uniqueness has been broken for more than half a decade already, with no fix in sight.

Simon - could you please post a link for me to read more about what this means. I don't follow how it's broken, but ,first, I'd like to know what typeclass coherence means.

Prof. Edwin Brady's Type-Driven Development with Idris book comments when discussing

 whether to put the `Ord` restraint on the data structure (Binary Tree) or the `insert` method:

Putting the constraint in the tree structure itself makes the type

more precise, in that it can now store only values which can be

compared at the nodes, at the cost of making it less reusable. This

is a tradeoff we often have to consider when defining new data

types.

[Simon Ochsenreither]

> I'd be wary to trust the conventional Haskell design approach given that type class coherence/confluence/uniqueness has been broken for more than half a decade already, with no fix in sight.

Simon - could you please post a link for me to read more about what this means. I don't follow how it's broken, but ,first, I'd like to know what typeclass coherence means.

Here is the ticket: https://ghc.haskell.org/trac/ghc/ticket/2356
Note the "Opened 8 years ago".

Basically, all the guarantees GHC gives about typeclasses are only valid for the "there is only a single module on this planet – ever" use-case.
 

Prof. Edwin Brady's Type-Driven Development with Idris book comments when discussing

 whether to put the `Ord` restraint on the data structure (Binary Tree) or the `insert` method:

Putting the constraint in the tree structure itself makes the type

more precise, in that it can now store only values which can be

compared at the nodes, at the cost of making it less reusable. This

is a tradeoff we often have to consider when defining new data

types.

That's a nice read! I agree with it. It's a tradeoff, not "OMG BUT PARAMETRICITY!!!" as some Haskell fans seem to believe. :-)

[Simon Ochsenreither]

> I'd be wary to trust the conventional Haskell design approach given that type class coherence/confluence/uniqueness has been broken for more than half a decade already, with no fix in sight.

Simon - could you please post a link for me to read more about what this means. I don't follow how it's broken, but ,first, I'd like to know what typeclass coherence means.

This is a nice blog post by Edward Yang who tries to describe what these terms mean: http://blog.ezyang.com/2014/07/type-classes-confluence-coherence-global-uniqueness/