Proposal: Introduce traits for for-comprehension


#1

It is not obvious what the various methods (foreach, flatMap, map, filter and withFilter) that need to be implemented for getting sequence or for comprehensions (these change depending on whether you are yielding or not or you support if or unapply etc etc).

The best documentation for this lives in a StackOverflow answer: http://stackoverflow.com/questions/1052476/what-is-scalas-yield/1059501#1059501

Why not simply put these special functions in couple of traits so it is obvious to the user which ones to implement to get the various comprehension features?


#2

The result (and even argument) types of these operations are not prescribed by the compiler. Any such trait would necessarily restrict what you could do with for-comprehensions.


#3

Also, it is often useful for these methods to take implicit parameters which allow smuggling some additional contextual information without changing the desugaring. The most obvious example is Future and ExecutionContext.

Various versions of for-comprehension magic methods may also accept different numbers of type parameters. There’s no way to express this level of freedom with just a couple of traits.


#4

Agree with the arguments given. In fact, both Haskell with the RebindableSyntax extension and Idris mirror Scala’s behavior — allow implementing do notation (Haskell’s for comprehensions) using methods that have different signatures.

Maybe you want to improve the existing documentation? All the relevant info is also in the language spec, though newbies won’t go there. I guess the documentation could include example signatures as starting point for your implementation, with similar documentation value—though I suspect the example signatures would essentially be a fragment of Traversable—in particular, FilterMonadic, or probably a version with simplified type signatures, without CanBuildFrom.


#5

Also, it is often useful for these methods to take implicit parameters which allow smuggling some additional contextual information without changing the desugaring. The most obvious example is Future and ExecutionContext.

Can’t we make the trait define map as

trait Mappable[T, C]{
  def map[V](f: T => V)(implicit ev: C)
}

Where C can be ExecutionContext for futures, ClassTag[T] for arrays, and DummyImplicit for everyone else? If something needs two implicits, then C can be SpecialImplicitBundle[A, B] defined as something like

  class SpecialImplicitBundle[T, T1[_], T2[_]]()(implicit val t1: T1[T], val t2: T2[T])
  object SpecialImplicitBundle{
    implicit def twoBounds[T, T1[_], T2[_]](implicit t1: T1[T], t2: T2[T]) = new SpecialImplicitBundle()(t1, t2)

    def apply[T, T1[_], T2[_]]()(implicit two: SpecialImplicitBundle[T, T1, T2]) = (two.t1, two.t2)
  }


#6

Hm, what’s the return type of map in your trait? This is hard to express in terms of subtyping … the resulting trait will be confusing to implement I think. If the point is to make this easier I think improving the doc is the way to do it.

Not surprisingly I think the useful abstraction here is Monad which is a type class (not a trait) and is well understood and supported by Cats and scalaz.


#7

What if there are more implicits? What if there are more type parameters? What if map is provided as an extension method? And most importantly, as @tpolecat already noted: what’s the return type of map?


#8

What if there are more implicits

Bundle them in nested SpecialImplicitBundles, and unpack them inside. This needs a bit of machinery but it works.

What if map is provided as an extension method?

What if? The class providing an extension method should be able to extend Mappable just fine, and then it’ll behave like any other non-extension Mappable.

what’s the return type of map in your trait?

I haven’t worked it out, but it seems it should be possible (though it may need another type param). Is there some reason to believe that such a signature is formally un-type-able?


#9

Just to clarify, I don’t that it’s the final answer. But I do think that something along this lines would probably work out, and haven’t really seen anything that tells me otherwise. The common reason I’ve heard is “what if there’s more than one implicit” which seems trivial to solve (with some boxing/bad-error-message cost) by introducing a Bundle implicit and unpacking it later.

Also, I don’t think that the signatures are pretty, and I do accept that with all the random type-params and stuff they would be confusing to implement. But I do think that all the complexity is just a formalization of the existing un-pretty-ness of the map method contract that people already have to implement, except now any errors appear at use-site rather than declaration-site.

I’m sure it’s possible that the desired semantics of a for-comprehension’s map is so dynamic it’s impossible to specify using traits (or type-classes, which to me are equivalent), but so far haven’t seen an argument that convinced me. My personal experience with Scala is that more often than not I’ve always been able to spec out semantics using traits, even for cases seemingly (?) more knotty/complex than this.


#10

You could probably create a Mappable trait that is general enough to support almost all or even all definitions of map out there. I hardly think that such a trait will make it easier for novices to implement the necessary methods.


#11

This seems like an unnecessary boilerplate further obfuscating the code.

I assumed that the compiler would require the target of map method to implement Mappable. But it’s true that it may as well look for implicit conversions.

Yes, we can add another type param. But what if map method itself is polymorphic? Totally normal situation is that map has type params on its own and the type of f and return type of map depend on them.

In such case Mappable would need higher-kinded type params. And if you want to have a one-to-rule-the-all signature, then you also need some form of kind polymorphism. And even if you have that, how do you express that the map method might have arbitrary number of type parameters of arbitrary kind with arbitrary bounds?

Even if it’s somehow possible, such trait would be so abstract that it would be completely incomprehensible and provide little value.


#12

Yeah – I think this is the point that’s getting lost in the discussion. The idea here was to make it easier to roll your own For-Things (what does one call Scala’s built-in kinda-sorta-Monad-concept?) with this trait; IMO, the conversation has mostly demonstrated that this probably isn’t the right way to achieve that goal…


#14

@lihaoyi Any chance you are trying to express more map methods using a generalization of CanBuildFrom? Because that’s what the direction it seems you’re going to. As others mentioned, that’s not very beginner-friendly.

For another example: embedded DSLs (like LMS or Slick lifted) can often end up with map methods using Rep, that can’t be expressed with the given Mappable, like the following (oversimplifying other details):

trait Collection[A] {
  def map[B](f: Rep[A] => Rep[B]): Collection[B]
}

Indeed, Mappable could abstract over that through higher-kinded type params.
The latest Slick lifted has weirder types that I don’t fully get, especially as they’re not uniform across map, flatMap and filter: http://slick.lightbend.com/doc/3.2.0/api/index.html#slick.lifted.Query.

@tpolecat:

Not surprisingly I think the useful abstraction here is Monad which is a type class (not a trait) and is well understood and supported by Cats and scalaz.

That does work when you get typeclasses. But we also understand well that the standard Monad typeclass is not general enough in Haskell. In Haskell, there’s a bunch of papers with variants of monads for various problems. Some of those (like restricted monads) can be subsumed with Monads over more general categories, but that’s also not beginner-friendly (I think most/all Haskell examples are in non-mainstream code, like subhask or Kmett’s packages).


#15

I realize Monad doesn’t express everything that you can do with a for comprehension, but it’s an immediate and broadly useful abstraction. My argument is mostly that trying to capture the generality of for using subtyping and higher-kinded F-bounded parameters and multi-parameter typeclasses like CBF and weird implicit coproducts is so complicated that it won’t be helpful. Just improve the doc and call it good.