Variance

[Runar Bjarnason]

I'm striving to add covariance to StateT. But this bleeds out to a whole host of things. For instance: traverseS:

  /** A version of `traverse` specialized for `State` */
  final def traverseS[S, B](f: A => State[S, B]): State[S, F[B]] =
    F.traverseS[S, A, B](self)(f)

This is defined in TraverseOps[F[_]], which must now become TraverseOps[F[+_]], and so Traverse[F[_]] must become Traverse[F[+_]] as well. And Unapply[TC[_[_]], FA] must become Unapply[TC[_[+_]], FA] as well. Same with Foldable.

Now, this is just a lot of work, but there are also inherent difficulties. Like for instance, Set is not covariant, so we can't make a Traverse[Set] anymore.

It would be really nice if a type class could simply be covariant in the *kind* of the type constructor. That is, maintain whatever the variance of the type constructor is, throughout. But in Scala, all kinds must be explicitly annotated. So we're kind of fucked.

Any ideas?


Runar

[Josh Suereth]

If you know you're not going to be violating variance rules, you can cheat to win:  @uncheckedVariance.  Look in the collection library for examples with all their crazy builder stuff.

- Josh

Runar

--
You received this message because you are subscribed to the Google Groups "scalaz" group.
To post to this group, send email to sca...@googlegroups.com.
To unsubscribe from this group, send email to scalaz+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/scalaz?hl=en.

[Runar Bjarnason]

!! Thx for teh cheat codez.

[Tony Morris]

lolz

[Matthew Pocock]

The problem with the set instance is, imho due to the library set being broken. Set should have the same variance as list but does not for historical reasons.

Runar

[Tony Morris]

That issue is not so simple.

Set, typically, is not a covariant functor. How would you performing the insert on reconstruction without element ordering?

[Josh Suereth]

No.   Covariance does not allow incoming values in Scala.   It's impossible to make a set that is Covariant.

i.e.   def contains(x: A): Boolean   // This A is in contravariant position.  You'd have to @uncheckedVariance it away.

- Josh

[Tony Morris]

Here is an interesting Olegistic citation for this issue of "Set not quite being a covariant Functor as it is often defined."

http://okmij.org/ftp/Haskell/types.html#restricted-datatypes

and interesting mailing list discussion:

http://www.haskell.org/pipermail/haskell-cafe/2010-July/080978.html

-- 
Tony Morris
http://tmorris.net/

[Eduardo Pareja Tobes]

IMHO, the problem lies in mixing

1. Set as the free commutative idempotent monoid monad, which is obviously covariant
2. Set as A => Boolean, which is obviously contravariant

Eduardo Pareja Tobes

eduardo.pareja-tobes.name <- that's me

oh no sequences! <- I work there

[Matthew Pocock]

On 11 May 2012 10:40, Eduardo Pareja Tobes <edu...@pareja-tobes.name> wrote:

IMHO, the problem lies in mixing

1. Set as the free commutative idempotent monoid monad, which is obviously covariant
2. Set as A => Boolean, which is obviously contravariant

Thanks. That is much more succinct than any explanation I would have come up with. IMHO, Set from your option 1 is what should be modelled as the data type, and there should be a projection Set[A] => A => Boolean for the latter. It is having Set[A] <:< A => Boolean that throws the spanner in the works, yet another example where OO inheritance seems on the surface to be convenient and expressive but gets you into trouble.

Matthew

--

Dr Matthew Pocock

Integrative Bioinformatics Group, School of Computing Science, Newcastle University

mailto: turingate...@gmail.com

gchat: turingate...@gmail.com

msn: matthew...@yahoo.co.uk

irc.freenode.net: drdozer

skype: matthew.pocock

tel: (0191) 2566550

mob: +447535664143

[Josh Suereth]

I don't disagree with this sentiment.  Unfortunately, Scala's collection library is a bit locked down in some aspects...

[Eduardo Pareja Tobes]

yes, from the point of view of collections I completely agree with 1. being what one really wants.

Eduardo Pareja Tobes

eduardo.pareja-tobes.name <- that's me

oh no sequences! <- I work there

[Luke Vilnis]

A frequent way to define sets though is church-encoding, so in those definitions the set _is_ the contains function - so it's not necessarily just object orientation that gets you into trouble here.

On Fri, May 11, 2012 at 11:46 AM, Matthew Pocock <turingate...@gmail.com> wrote:

[Chris Marshall]

I think scala made *absolutely* the right choice. I use set frequently as an implementation of A => Boolean, and want to use predicate-like ops on it. It's much rarer that I care about its lack of covariance.

Chris

[Tony Morris]

I might have missed something. What choice are we discussing exactly? Is
it for Set[A] to extend A => Boolean, because that's just really really
silly.

For Set and variance, Set is neither covariant nor contravariant
functor. It is one of these though:

trait OrdFunctor[F[_]] {
def ordfmap[A: Order, B: Order](f: A => B): F[A] => F[B]
}

Now, it might be said, "but it's a hash-based set" or something like it,
but then that doesn't make it a functor either -- you now have to carry
the hashing function (rather than the ordering). Furthermore, the Set
operations are then likely to be in ST for performance reasons.

Sorry if I'm a bit off-track.