# Using generalised type constraints in 2.8 collections

In light of generalised type constraints:

- Should List.flatten be tightened to accept 'implicit ev: A <:< Iterable[B]' rather than 'implicit f : A => Iterable[B]'?
- Could we have Option.flatten, along the lines of: http://gist.github.com/228927  ?

Or am I just wielding a shiny new hammer in search of things resembilng nails?

-jason

### Re: Using generalised type constraints in 2.8 collections

On Sun, Nov 8, 2009 at 12:08 AM, Jason Zaugg <jzaugg [at] gmail [dot] com> wrote:
In light of generalised type constraints:

- Should List.flatten be tightened to accept 'implicit ev: A <:< Iterable[B]' rather than 'implicit f : A => Iterable[B]'?
- Could we have Option.flatten, along the lines of: http://gist.github.com/228927  ?

Or am I just wielding a shiny new hammer in search of things resembilng nails?
nope! nail: meet hammer; hammer: meet flatten
i'll look into it in the next couple of days
thanks!

### Re: Using generalised type constraints in 2.8 collections

On Sun, Nov 08, 2009 at 05:44:19PM +0100, Adriaan Moors wrote:
> > - Should List.flatten be tightened to accept 'implicit ev: A <:<
> > Iterable[B]' rather than 'implicit f : A => Iterable[B]'?
>
> nope! nail: meet hammer; hammer: meet flatten

I'm sure you'll both notice if you haven't already that the current type
signature of flatten is:

def flatten[B](implicit asTraversable: A => /*<: val x: Either[Either[Int, String], String] = Left(Right("a"))
x: Either[Either[Int,String],String] = Left(Right(a))

Without some means to limit the type of A "from the inside", flattening
had to be done like this:

scala> Either.joinLeft(x)
res1: Either[Int,String] = Right(a)

Now the method is on the instance:

scala> x.joinLeft
res0: Either[Int,String] = Right(a)

With this signature:

def joinLeft[A1 >: A, B1 >: B, C](implicit ev: A1 <:< Either[C, B1]): Either[C, B1]

### Re: Using generalised type constraints in 2.8 collections

I'm sure you'll both notice if you haven't already that the current type
signature of flatten is:

def flatten[B](implicit asTraversable: A => /*<:<!!!*/ Traversable[B]): CC[B] = {

which has that definite ring of "didn't work for some reason."
it didn't work back then because there were some subtleties with the coup d'état that removed identity from its implicit pedestal in favour of <:< (bootstrapping issues, as you might imagine).
That's history now, so nothing (should be) stopping you (or me, of course) from doing the obvious search/replace.

### Re: Using generalised type constraints in 2.8 collections

On Sun, Nov 08, 2009 at 07:40:05PM +0100, Adriaan Moors wrote:
> > def flatten[B](implicit asTraversable: A => /*<: >
> it didn't work back then because there were some subtleties with the
> coup d'état that removed identity from its implicit pedestal in
> favour of <:< (bootstrapping issues, as you might imagine).

Hmmm. Such a definition excludes Option, which is as we know too well
not actually a Traversable, but converts to one.

So my oft-used List(Some(5), None).flatten no longer compiles.

### Re: Using generalised type constraints in 2.8 collections

good point. it's a tricky design decision -- do we want subtyping or convertibility?we could introduce <?< (or something better ascii-art welcome), but I'm definitely against going back to =>, as it conflates views and bounds (as witnessed by implicit values)
<?< would include <:<, as well as conversions such Option[A] <?< Traversable[A]
On Sun, Nov 8, 2009 at 8:45 PM, Paul Phillips <paulp [at] improving [dot] org> wrote:
On Sun, Nov 08, 2009 at 07:40:05PM +0100, Adriaan Moors wrote:
> >  def flatten[B](implicit asTraversable: A => /*<:<!!!*/ Traversable[B]):
> >
> it didn't work back then because there were some subtleties with the
> coup d'état that removed identity from its implicit pedestal in
> favour of <:< (bootstrapping issues, as you might imagine).

Hmmm.  Such a definition excludes Option, which is as we know too well
not actually a Traversable, but converts to one.

So my oft-used List(Some(5), None).flatten no longer compiles.

--
Paul Phillips      | A national political campaign is better than the
Apatheist          | best circus ever heard of, with a mass baptism and
Empiricist         | a couple of hangings thrown in.
pal, i pill push   |     -- H. L. Mencken

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

### Re: Using generalised type constraints in 2.8 collections

On Sun, Nov 8, 2009 at 9:02 PM, Adriaan Moors <adriaan [dot] moors [at] cs [dot] kuleuven [dot] be> wrote:
good point. it's a tricky design decision -- do we want subtyping or convertibility?we could introduce <?< (or something better ascii-art welcome), but I'm definitely against going back to =>, as it conflates views and bounds (as witnessed by implicit values)
<?< would include <:<, as well as conversions such Option[A] <?< Traversable[A]

<%< ?

On Sun, Nov 8, 2009 at 8:45 PM, Paul Phillips <paulp [at] improving [dot] org> wrote:
On Sun, Nov 08, 2009 at 07:40:05PM +0100, Adriaan Moors wrote:
> >  def flatten[B](implicit asTraversable: A => /*<:<!!!*/ Traversable[B]):
> >
> it didn't work back then because there were some subtleties with the
> coup d'état that removed identity from its implicit pedestal in
> favour of <:< (bootstrapping issues, as you might imagine).

Hmmm.  Such a definition excludes Option, which is as we know too well
not actually a Traversable, but converts to one.

So my oft-used List(Some(5), None).flatten no longer compiles.

--
Paul Phillips      | A national political campaign is better than the
Apatheist          | best circus ever heard of, with a mass baptism and
Empiricist         | a couple of hangings thrown in.
pal, i pill push   |     -- H. L. Mencken

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

--
Viktor Klang
| "A complex system that works is invariably
| found to have evolved from a simple system
| that worked." - John Gall

Blog: klangism.blogspot.com
Code: github.com/viktorklang

### Re: Using generalised type constraints in 2.8 collections

In general, the flexibility to choose <:< or <%< would be useful. The former ought to be the default choice for a type-fearing API designer, but consideration of backwards compatibility and flexibility could swing the decision other way. I guess you could even sit on the fence, make the type abstract and let the user decide :)

For completeness, perhaps ==[A, B] should be included: http://article.gmane.org/gmane.comp.lang.scala.user/18879

In this particular case, I would find one of the following more intention revealing.

List(Some(1), None).filterMap { case Some(x) => x }

Which perhaps warrants its own function:

Option.somes(List(Some(5), None))

or, granting Option a(nother) ticket into TraversibleLike:

List(Some(5), None).somes

-jason

On Sun, Nov 8, 2009 at 9:47 PM, Viktor Klang <viktor [dot] klang [at] gmail [dot] com> wrote:

On Sun, Nov 8, 2009 at 9:02 PM, Adriaan Moors <adriaan [dot] moors [at] cs [dot] kuleuven [dot] be> wrote:
good point. it's a tricky design decision -- do we want subtyping or convertibility?we could introduce <?< (or something better ascii-art welcome), but I'm definitely against going back to =>, as it conflates views and bounds (as witnessed by implicit values)
<?< would include <:<, as well as conversions such Option[A] <?< Traversable[A]

<%< ?

On Sun, Nov 8, 2009 at 8:45 PM, Paul Phillips <paulp [at] improving [dot] org> wrote:
On Sun, Nov 08, 2009 at 07:40:05PM +0100, Adriaan Moors wrote:
> >  def flatten[B](implicit asTraversable: A => /*<:<!!!*/ Traversable[B]):
> >
> it didn't work back then because there were some subtleties with the
> coup d'état that removed identity from its implicit pedestal in
> favour of <:< (bootstrapping issues, as you might imagine).

Hmmm.  Such a definition excludes Option, which is as we know too well
not actually a Traversable, but converts to one.

So my oft-used List(Some(5), None).flatten no longer compiles.

--
Paul Phillips      | A national political campaign is better than the
Apatheist          | best circus ever heard of, with a mass baptism and
Empiricist         | a couple of hangings thrown in.
pal, i pill push   |     -- H. L. Mencken

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

--
Viktor Klang
| "A complex system that works is invariably
| found to have evolved from a simple system
| that worked." - John Gall

Blog: klangism.blogspot.com
Code: github.com/viktorklang

### Re: Using generalised type constraints in 2.8 collections

It occurs to me that defining implicits to generate <:<, <%< and == in Predef would lead to ambiguity if you required A => B. So <%< and == should be defined on the companion objects:

sealed abstract class <:<[-From, +To] extends (From => To)
object <:< {
implicit def conforms[A]: A <:< A = new (A <:< A) {def apply(x: A) = x} }

sealed abstract class =:=[A, B]
object =:= {   implicit def tpEq[A]: A =:= A = new (A =:= A) { def apply(a: A): A = a }
}
sealed abstract class <%<[A, B]
object <%< {   implicit def tpView[A <% B, B]: A <%< B = new (A <%< B) { def apply(a: A): B = a }
}

On Sun, Nov 8, 2009 at 9:50 PM, Jason Zaugg <jzaugg [at] gmail [dot] com> wrote:
In general, the flexibility to choose <:< or <%< would be useful. The former ought to be the default choice for a type-fearing API designer, but consideration of backwards compatibility and flexibility could swing the decision other way. I guess you could even sit on the fence, make the type abstract and let the user decide :)

For completeness, perhaps ==[A, B] should be included: http://article.gmane.org/gmane.comp.lang.scala.user/18879

In this particular case, I would find one of the following more intention revealing.

List(Some(1), None).filterMap { case Some(x) => x }

Which perhaps warrants its own function:

Option.somes(List(Some(5), None))

or, granting Option a(nother) ticket into TraversibleLike:

List(Some(5), None).somes

-jason

On Sun, Nov 8, 2009 at 9:47 PM, Viktor Klang <viktor [dot] klang [at] gmail [dot] com> wrote:

On Sun, Nov 8, 2009 at 9:02 PM, Adriaan Moors <adriaan [dot] moors [at] cs [dot] kuleuven [dot] be> wrote:
good point. it's a tricky design decision -- do we want subtyping or convertibility?we could introduce <?< (or something better ascii-art welcome), but I'm definitely against going back to =>, as it conflates views and bounds (as witnessed by implicit values)
<?< would include <:<, as well as conversions such Option[A] <?< Traversable[A]

<%< ?

On Sun, Nov 8, 2009 at 8:45 PM, Paul Phillips <paulp [at] improving [dot] org> wrote:
On Sun, Nov 08, 2009 at 07:40:05PM +0100, Adriaan Moors wrote:
> >  def flatten[B](implicit asTraversable: A => /*<:<!!!*/ Traversable[B]):
> >
> it didn't work back then because there were some subtleties with the
> coup d'état that removed identity from its implicit pedestal in
> favour of <:< (bootstrapping issues, as you might imagine).

Hmmm.  Such a definition excludes Option, which is as we know too well
not actually a Traversable, but converts to one.

So my oft-used List(Some(5), None).flatten no longer compiles.

--
Paul Phillips      | A national political campaign is better than the
Apatheist          | best circus ever heard of, with a mass baptism and
Empiricist         | a couple of hangings thrown in.
pal, i pill push   |     -- H. L. Mencken

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

--
Viktor Klang
| "A complex system that works is invariably
| found to have evolved from a simple system
| that worked." - John Gall

Blog: klangism.blogspot.com
Code: github.com/viktorklang

### Re: Using generalised type constraints in 2.8 collections

Sorry, hit send too soon. Here's working code:

http://gist.github.com/229756

sealed abstract class <:<[-From, +To] extends (From => To)
object <:< {
implicit def conforms[A]: A <:< A = new (A <:< A) {def apply(x: A) = x}
}

sealed abstract class ==[From, To] extends (From => To)
object == {
implicit def tpEquals[A]: A == A = new (A == A) {def apply(x: A) = x}
}

sealed abstract class <%<[-From, +To] extends (From => To)
object <%< {
implicit def conformsOrViewsAs[A <% B, B]: A <%< B = new (A <%< B) {def apply(x: A) = x}
}

trait A
trait B
implicit def AToB(a: A): B = new B {}

println(implicitly[Int == Int], implicitly[Int <:< Any], implicitly[A <%< B])

//object Predef {
implicit def identity[A](a: A): A = a
//}

println((implicitly[Int => Int], implicitly[Int => Any]))

On Mon, Nov 9, 2009 at 8:02 AM, Jason Zaugg <jzaugg [at] gmail [dot] com> wrote:
It occurs to me that defining implicits to generate <:<, <%< and == in Predef would lead to ambiguity if you required A => B. So <%< and == should be defined on the companion objects:

### Re: Using generalised type constraints in 2.8 collections

On Sun, Nov 8, 2009 at 12:08 AM, Jason Zaugg wrote:
> In light of generalised type constraints:
Are these somewhere documented? What do they do?

### Re: Using generalised type constraints in 2.8 collections

Here's a demo of what they enable, showing the equivalent Scala 2.7 code. http://gist.github.com/229163

In 2.7 and 2.8, <: allows you to constraint type parameters of the current method. But to constrain other in-scope abstract types, you needed to add an implicit parameter to the method (see List.flatten.)

In 2.7, you could require an implicit of type (A => B) and expect this implicit to be provided by Predef.identity. But it could also come from other in scope implicit conversion functions. Requiring a parameter of (A <:< B) is stricter because the instances can only be generated if A conforms to B.

As far as I can tell, it is just a library change to Predef, no compiler magic at all.

2.7:
Predef.scala
implicit def identity[A](x: A): A = x

2.8
Predef.scala
sealed abstract class <:<[-From, +To] extends (From => To)
implicit def conforms[A]: A <:< A = new (A <:< A) {def apply(x: A) = x}

-jason

On Sun, Nov 8, 2009 at 4:35 PM, Johannes Rudolph <johannes [dot] rudolph [at] googlemail [dot] com> wrote:
On Sun, Nov 8, 2009 at 12:08 AM, Jason Zaugg <jzaugg [at] gmail [dot] com> wrote:
> In light of generalised type constraints:
Are these somewhere documented? What do they do?

--
Johannes

-----------------------------------------------
Johannes Rudolph
http://virtual-void.net