Either.merge

On Wednesday 24 June 2009 13:07, Miles Sabin wrote:
> Is there any particularly good reason why merge is currently defined
> on Either's companion object as,
>
> def merge[T](e: Either[T, T]) = e match {
> case Left(t) => t
> case Right(t) => t
> }
>
> rather than directly on Either as,
>
> def merge = this match {
> case Left(a) => a
> case Right(b) => b
> }
>
> Cheers,
>
>
> Miles
>

The return type of the version on the companion object is T. The return type
of the version directly on Either is Any. For an argument of type
Either[A,B], T could be a more specific common supertype of A and B than Any.

-Mark

On Wed, Jun 24, 2009 at 06:07:03PM +0100, Miles Sabin wrote:
> Is there any particularly good reason why merge is currently defined
> on Either's companion object as,

As nearly as I can tell: if you define it on the class, you will get an
Any, but on the companion object you get something more sensible.

scala> var x: Either[List[Int], Map[Int,Int]] = Left(List(1))
x: Either[List[Int],Map[Int,Int]] = Left(List(1))

scala> Either.merge(x)
res0: scala.collection.immutable.Iterable[Any] with PartialFunction[Int,Int] = List(1)

...but maybe that's just because I can't figure out how to write it on
the class to get it to perform the same unification.

It could be 'on' the Either through an implicit.

implicit def either2Mergable[T](e: Either[T, T]) = new { def merge = e
fold (_, _) } .. or similar

2009/6/24 Paul Phillips :
> On Wed, Jun 24, 2009 at 06:07:03PM +0100, Miles Sabin wrote:
>> Is there any particularly good reason why merge is currently defined
>> on Either's companion object as,
>
> As nearly as I can tell: if you define it on the class, you will get an
> Any, but on the companion object you get something more sensible.
>
> scala> var x: Either[List[Int], Map[Int,Int]] = Left(List(1))
> x: Either[List[Int],Map[Int,Int]] = Left(List(1))
>
> scala> Either.merge(x)
> res0: scala.collection.immutable.Iterable[Any] with PartialFunction[Int,Int] = List(1)
>
> ...but maybe that's just because I can't figure out how to write it on
> the class to get it to perform the same unification.
>
> --
> Paul Phillips      | It's better to have gloved and tossed than never to
> Caged Spirit       | have played baseball.
> Empiricist         |
> i pull his palp!   |----------* http://www.improving.org/paulp/ *----------
>

On Wed, Jun 24, 2009 at 6:47 PM, Paul Phillips wrote:
> On Wed, Jun 24, 2009 at 06:07:03PM +0100, Miles Sabin wrote:
>> Is there any particularly good reason why merge is currently defined
>> on Either's companion object as,
>
> As nearly as I can tell: if you define it on the class, you will get an
> Any, but on the companion object you get something more sensible.
>
> scala> var x: Either[List[Int], Map[Int,Int]] = Left(List(1))
> x: Either[List[Int],Map[Int,Int]] = Left(List(1))
>
> scala> Either.merge(x)
> res0: scala.collection.immutable.Iterable[Any] with PartialFunction[Int,Int] = List(1)

Hmm ... interesting ... I'd assumed the LUB of A and B would be
inferred as the return type.

> ...but maybe that's just because I can't figure out how to write it on
> the class to get it to perform the same unification.

The following rather ugly looking thing seems to do the trick,

case class Phantom[+T]()

sealed abstract class Either[+A, +B] {

// ...

def merge[T](l : Phantom[T] = Phantom[A](), r : Phantom[T] =
Phantom[B]()) : T = (this match {
case Left(a) => a
case Right(b) => b
}).asInstanceOf[T] // Apparently redundant asInstanceOf required

// ...
}

Cheers,

Miles

On Wed, Jun 24, 2009 at 9:14 PM, Ricky Clarkson wrote:
> It could be 'on' the Either through an implicit.
>
> implicit def either2Mergable[T](e: Either[T, T]) = new { def merge = e
> fold (_, _) } .. or similar

So what's missing that allows us to express this via an implicit, but
not as an explicit method on the class?

Cheers,

Miles

The notion of methods that only exist when type parameters match a
rule (e.g., A == B in this case).

2009/6/25 Miles Sabin :
> On Wed, Jun 24, 2009 at 9:14 PM, Ricky Clarkson wrote:
>> It could be 'on' the Either through an implicit.
>>
>> implicit def either2Mergable[T](e: Either[T, T]) = new { def merge = e
>> fold (_, _) } .. or similar
>
> So what's missing that allows us to express this via an implicit, but
> not as an explicit method on the class?
>
> Cheers,
>
>
> Miles
>
> --
> Miles Sabin
> tel: +44 (0)7813 944 528
> skype:  milessabin
> http://www.chuusai.com/
> http://twitter.com/milessabin
>

On Thu, Jun 25, 2009 at 10:39 AM, Ricky
Clarkson wrote:
> The notion of methods that only exist when type parameters match a
> rule (e.g., A == B in this case).
>
Exactly. There's an interesting paper by Kennedy and Russo
that proposed an extension to the C# type system with generalized type
constraints. With that extension idioms like Either.merge could be
expressed. AFAIK it's not part of the official C#, though. In Scala,
implicits can be used to achieve an analogous effect. I think it would
make sense to implicitly add merge as a method of Either.

Cheers

It also wouldn't add an awful lot to C#, as extension methods can
already do that in a similar way to how implicits can for Scala.

public static T Merge(Either e) { return e.Fold(t => t, t =>
t); } //assuming Mono.Rocks.Either

2009/6/25 martin odersky :
> On Thu, Jun 25, 2009 at 10:39 AM, Ricky
> Clarkson wrote:
>> The notion of methods that only exist when type parameters match a
>> rule (e.g., A == B in this case).
>>
> Exactly. There's an interesting paper by Kennedy and Russo
> that proposed an extension to the C# type system with generalized type
> constraints. With that extension idioms like Either.merge could be
> expressed. AFAIK it's not part of the official C#, though. In Scala,
> implicits can be used to achieve an analogous effect. I think it would
> make sense to implicitly add merge as a method of Either.
>
> Cheers
>
>  -- Martin
>
> Andrew Kennedy, Claudio V. Russo: Generalized algebraic data types and
> object-oriented programming. OOPSLA 2005: 21-40
>

Whoops. I forgot the 'this'. I'll fix that and add an example:

public static T Merge(this Either e) { return e.Fold(t => t, t => t); }

Either foo = ...;
var response = foo.Merge();

Sometimes I wish Scala had extension methods, even though implicits
can do everything extension methods can. It seems more direct an
approach.

2009/6/25 Ricky Clarkson :
> It also wouldn't add an awful lot to C#, as extension methods can
> already do that in a similar way to how implicits can for Scala.
>
> public static T Merge(Either e) { return e.Fold(t => t, t =>
> t); } //assuming Mono.Rocks.Either
>
> 2009/6/25 martin odersky :
>> On Thu, Jun 25, 2009 at 10:39 AM, Ricky
>> Clarkson wrote:
>>> The notion of methods that only exist when type parameters match a
>>> rule (e.g., A == B in this case).
>>>
>> Exactly. There's an interesting paper by Kennedy and Russo
>> that proposed an extension to the C# type system with generalized type
>> constraints. With that extension idioms like Either.merge could be
>> expressed. AFAIK it's not part of the official C#, though. In Scala,
>> implicits can be used to achieve an analogous effect. I think it would
>> make sense to implicitly add merge as a method of Either.
>>
>> Cheers
>>
>>  -- Martin
>>
>> Andrew Kennedy, Claudio V. Russo: Generalized algebraic data types and
>> object-oriented programming. OOPSLA 2005: 21-40
>>
>
>
>
> --
> Ricky Clarkson
> Java Programmer, AD Holdings
> +44 1565 770804
> Skype: ricky_clarkson
> Google Talk: ricky.clarkson@gmail.com
>

There's a SIP in progress for something like that:

http://jorgeortiz85.github.com/ImplicitClassSIP.xhtml

On Thu, Jun 25, 2009 at 11:57 AM, Ricky Clarkson <ricky.clarkson@gmail.com> wrote:

Whoops.  I forgot the 'this'.  I'll fix that and add an example:

public static T Merge<T>(this Either<T, T> e) { return e.Fold(t => t, t => t); }

Either<string, string> foo = ...;
var response = foo.Merge();

Sometimes I wish Scala had extension methods, even though implicits
can do everything extension methods can.  It seems more direct an
approach.

2009/6/25 Ricky Clarkson <ricky.clarkson@gmail.com>:
> It also wouldn't add an awful lot to C#, as extension methods can
> already do that in a similar way to how implicits can for Scala.
>
> public static T Merge<T>(Either<T, T> e) { return e.Fold(t => t, t =>
> t); } //assuming Mono.Rocks.Either
>
> 2009/6/25 martin odersky <martin.odersky@epfl.ch>:
>> On Thu, Jun 25, 2009 at 10:39 AM, Ricky
>> Clarkson<ricky.clarkson@gmail.com> wrote:
>>> The notion of methods that only exist when type parameters match a
>>> rule (e.g., A == B in this case).
>>>
>> Exactly. There's an interesting paper by Kennedy and Russo
>> that proposed an extension to the C# type system with generalized type
>> constraints. With that extension idioms like Either.merge could be
>> expressed. AFAIK it's not part of the official C#, though. In Scala,
>> implicits can be used to achieve an analogous effect. I think it would
>> make sense to implicitly add merge as a method of Either.
>>
>> Cheers
>>
>>  -- Martin
>>
>> Andrew Kennedy, Claudio V. Russo: Generalized algebraic data types and
>> object-oriented programming. OOPSLA 2005: 21-40
>>
>
>
>
> --
> Ricky Clarkson
> Java Programmer, AD Holdings
> +44 1565 770804
> Skype: ricky_clarkson
> Google Talk: ricky.clarkson@gmail.com
>



--
Ricky Clarkson
Java Programmer, AD Holdings
+44 1565 770804
Skype: ricky_clarkson
Google Talk: ricky.clarkson@gmail.com

--
Viktor Klang
Scala Loudmouth

On Thu, Jun 25, 2009 at 10:00 AM, martin odersky wrote:
> On Thu, Jun 25, 2009 at 10:39 AM, Ricky
> Clarkson wrote:
>> The notion of methods that only exist when type parameters match a
>> rule (e.g., A == B in this case).
>>
> Exactly. There's an interesting paper by Kennedy and Russo
> that proposed an extension to the C# type system with generalized type
> constraints.

Yes, but that seems a bit heavyweight in this case: all we really need
to do here is compute the LUB of the two type parameters,

def merge : LUB[A, B] = ...

Is there any way of expressing that in current Scala?

Cheers,

Miles

On Thu, Jun 25, 2009 at 12:13 PM, Miles Sabin <miles@milessabin.com> wrote:

On Thu, Jun 25, 2009 at 10:00 AM, martin odersky<martin.odersky@epfl.ch> wrote:
> On Thu, Jun 25, 2009 at 10:39 AM, Ricky
> Clarkson<ricky.clarkson@gmail.com> wrote:
>> The notion of methods that only exist when type parameters match a
>> rule (e.g., A == B in this case).
>>
> Exactly. There's an interesting paper by Kennedy and Russo
> that proposed an extension to the C# type system with generalized type
> constraints.

Yes, but that seems a bit heavyweight in this case: all we really need
to do here is compute the LUB of the two type parameters,

 def merge : LUB[A, B] = ...

Is there any way of expressing that in current Scala?

I couldn't come up with a better approach than simply encoding generalised type constraints:
object Test {
// a witness to subtyping, only one way to construct it (SubWitness):sealed abstract class <:<[-From, +To] extends (From=>To)  {def apply(x: From): To}  final class SubWitness[T] extends <:<[T, T] {def apply(x: T): T = x} // could future version of optimiser eliminate the run-time impact fully?
// implicit argument of type A <:< B requires witness of type T <:< T, // where T <:< T <: A <:< B, thus A <: T and T <: B, and, by transitivity: A <: B implicit def subWitness[T] = new SubWitness[T]// can't reuse existing implicits in Predef because they are ambiguous

trait Either[+A, +B] {   def a: A = error("meh")    def b: B = error("meh")      def merge[C](implicit c1: A <:< C, c2: B <:< C): C   // def merge[C]: C where A <: C /\ B <: C}
case class Left[A](override val a: A) extends Either[A, Nothing] {   def merge[C](implicit c1: A <:< C, c2: Nothing <:< C): C = a   // def merge[C]: C where A <: C = a}
case class Right[B](override val b: B) extends Either[Nothing, B] {   def merge[C](implicit c1: Nothing <:< C, c2: B <:< C): C = b   // def merge[C]: C where B <: C = b }
val x = Left(1) merge
val dunno: Either[Int, String] = Right("hi")val y: Any = dunno merge
//val y = dunno merge // type inference fails, even though we can figure out C if we take implicits into account, as  // it must be the lub of Int and String for implicit resolution to work// --> unify type inference (implicit type search) and implicits search (value inference)?}
cheers, adriaan

On Thu, Jun 25, 2009 at 11:13 AM, Miles Sabin wrote:
> Yes, but that seems a bit heavyweight in this case: all we really need
> to do here is compute the LUB of the two type parameters,
>
>  def merge : LUB[A, B] = ...
>
> Is there any way of expressing that in current Scala?

Why doesn't the following do the trick?

def merge = {
def aux[T](a : Option[T], b : Option[T]) : T = a.getOrElse(b.get)
aux(left.toOption, right.toOption)
}

In this case shouldn't A and B be unified to their LUB by aux its type
taken as the type of merge?

For that matter, why does,

def merge = Either.merge(this)

not do it? Like the previous variation, the type of merge ends up as Any.

Cheers,

Miles

afaict, the inferred type for your definition of merge is:
Either[S, T] => Any
whereas mine has type 
Either[S, T] => C where S <: C /\ T <: C  (using syntactic sugar, of course, to represent the implicit args)
in case S =:= T, C is inferred to be S  (when they differ, you need to compute the LUB yourself and give an explicit type annotation, but it need not be Any -- I think it would be interesting to fuse type inference and implicits search, so these types could be inferred too)
concretely, in my example Left(1) merge : Int, whereas I think it would have type Any with your definition
as another example, consider:
class X class A extends X class B extends X 
val aorb: Either[A, B] = Left(new A)val z : X = aorb merge // I don't think this would type check with your definition
cheersadriaan

On Thu, Jun 25, 2009 at 7:31 PM, Miles Sabin <miles@milessabin.com> wrote:

On Thu, Jun 25, 2009 at 11:13 AM, Miles Sabin<miles@milessabin.com> wrote:
> Yes, but that seems a bit heavyweight in this case: all we really need
> to do here is compute the LUB of the two type parameters,
>
>  def merge : LUB[A, B] = ...
>
> Is there any way of expressing that in current Scala?

Why doesn't the following do the trick?

 def merge = {
   def aux[T](a : Option[T], b : Option[T]) : T = a.getOrElse(b.get)
   aux(left.toOption, right.toOption)
 }

In this case shouldn't A and B be unified to their LUB by aux its type
taken as the type of merge?

For that matter, why does,

 def merge = Either.merge(this)

not do it? Like the previous variation, the type of merge ends up as Any.

Cheers,


Miles

--
Miles Sabin
tel: +44 (0)7813 944 528
skype:  milessabin
http://www.chuusai.com/
http://twitter.com/milessabin


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

On Thu, Jun 25, 2009 at 7:06 PM, Adriaan
Moors wrote:
> afaict, the inferred type for your definition of merge is:
> Either[S, T] => Any

Well, yes, but why is that so when then type for Either.merge on the
companion object is the desired LUB of the type parameters?

Cheers,

Miles

2009/6/25 Miles Sabin :
> On Thu, Jun 25, 2009 at 7:06 PM, Adriaan
> Moors wrote:
>> afaict, the inferred type for your definition of merge is:
>> Either[S, T] => Any
>
> Well, yes, but why is that so when then type for Either.merge on the
> companion object is the desired LUB of the type parameters?

Note that the same thing happens if you call merge anywhere else with
type parameters instead of concrete types:

scala> def foo[S, T](e : Either[S, T]) = Either.merge(e)
foo: [S,T](Either[S,T])Any

The reason merge works sometimes is because it's being called with two
*concrete* types which thus have a better lower bound than Any. When
there's not more information about the types it's called with you end
up with the Any upper bound again.

in general there's no way in Scala to go from two types to their LUB,
so you end up with situations like this where a non-ideal upper bound
may have to be inferred.

On Thu, Jun 25, 2009 at 10:31 PM, David MacIver wrote:
> in general there's no way in Scala to go from two types to their LUB,
> so you end up with situations like this where a non-ideal upper bound
> may have to be inferred.

Not so: the frankenstein version I gave earlier using phantom types
and default arguments works just fine ... so the compiler pretty
clearly does have the relevant information.

Cheers,

Miles

2009/6/25 Miles Sabin :
> On Thu, Jun 25, 2009 at 10:31 PM, David MacIver wrote:
>> in general there's no way in Scala to go from two types to their LUB,
>> so you end up with situations like this where a non-ideal upper bound
>> may have to be inferred.
>
> Not so: the frankenstein version I gave earlier using phantom types
> and default arguments works just fine ... so the compiler pretty
> clearly does have the relevant information.

It's not a question of relevant information: There's no way to write
down the type.

On Thu, Jun 25, 2009 at 10:44 PM, David MacIver wrote:
> 2009/6/25 Miles Sabin :
>> Not so: the frankenstein version I gave earlier using phantom types
>> and default arguments works just fine ... so the compiler pretty
>> clearly does have the relevant information.
>
> It's not a question of relevant information: There's no way to write
> down the type.

That doesn't matter because we don't have to write down the type. With
the version of merge I mentioned just now we get the following
interpreter session,

miles@lewis:scala$ dists/latest/bin/scala
Welcome to Scala version 2.8.0.r18101-b20090625224704 (Java
HotSpot(TM) Server VM, Java 1.6.0_10).
Type in expressions to have them evaluated.
Type :help for more information.

scala> var x: Either[List[Int], Map[Int,Int]] = Left(List(1))
x: Either[List[Int],Map[Int,Int]] = Left(List(1))

scala> x.merge()
res0: scala.collection.immutable.Iterable[Any] with
PartialFunction[Int,Int] = List(1)

scala>

You can clearly see that the compiler has inferred the LUB and
propagated it to the calling context.

Cheers,

Miles

2009/6/25 Miles Sabin :
> On Thu, Jun 25, 2009 at 10:44 PM, David MacIver wrote:
>> 2009/6/25 Miles Sabin :
>>> Not so: the frankenstein version I gave earlier using phantom types
>>> and default arguments works just fine ... so the compiler pretty
>>> clearly does have the relevant information.
>>
>> It's not a question of relevant information: There's no way to write
>> down the type.
>
> That doesn't matter because we don't have to write down the type. With
> the version of merge I mentioned just now we get the following
> interpreter session,
>
> miles@lewis:scala$ dists/latest/bin/scala
> Welcome to Scala version 2.8.0.r18101-b20090625224704 (Java
> HotSpot(TM) Server VM, Java 1.6.0_10).
> Type in expressions to have them evaluated.
> Type :help for more information.
>
> scala> var x: Either[List[Int], Map[Int,Int]] = Left(List(1))
> x: Either[List[Int],Map[Int,Int]] = Left(List(1))
>
> scala> x.merge()
> res0: scala.collection.immutable.Iterable[Any] with
> PartialFunction[Int,Int] = List(1)
>
> scala>
>
> You can clearly see that the compiler has inferred the LUB and
> propagated it to the calling context.

No, it has inferred the LUB in the calling context. It hasn't inferred
it in the defining context, because there is no way for it to do so
there. All of the various ways of making this work do so because they
hold off the calculation of the LUB until a point where it can be
guaranteed to exist.

On Thu, Jun 25, 2009 at 11:30 PM, David MacIver wrote:
> No, it has inferred the LUB in the calling context. It hasn't inferred
> it in the defining context, because there is no way for it to do so
> there. All of the various ways of making this work do so because they
> hold off the calculation of the LUB until a point where it can be
> guaranteed to exist.

From the point of view of the usability of a merge method defined on
instances of Either I really don't see why this is relevant. The merge
method I posted is ugly but does the right thing, and there don't seem
to be any obvious alternatives. Another example (the one I was really
aiming at),

miles@lewis:scala$ dists/latest/bin/scala
Welcome to Scala version 2.8.0.r18101-b20090625224704 (Java
HotSpot(TM) Server VM, Java 1.6.0_10).
Type in expressions to have them evaluated.
Type :help for more information.

scala> class Base
defined class Base

scala> class Derived1 extends Base
defined class Derived1

scala> class Derived2 extends Base
defined class Derived2

scala> val l : List[Either[Derived1, Derived2]] = List(Left(new
Derived1), Right(new Derived2))
l: List[Either[Derived1,Derived2]] = List(Left(Derived1@30f369),
Right(Derived2@1bc850f))

scala> l.map(_.merge())
res0: List[Base] = List(Derived1@30f369, Derived2@1bc850f)

Nb. I'm really not suggesting that we add the monstrosity that I
concocted to Either, but the fact that it works the way that I've
shown suggests that Scala's type inference rules could be tweaked to
produce more precise (and useful) results.

Cheers,

Miles