Simulating a disjunction (union) type in Scala

[Shelby]

Regarding comments 23 and 35 of [Mile Sabin's solution][1], here is a
way to declare a union type at the use site. Note it is unboxed after
the first level, i.e. it has the advantage being [extensible to any
number of types in the disjunction][2], whereas `Either` needs nested
boxing and the paradigm in my prior comment 41 was not extensible. In
other words, a `D[Int ∨ String]` is assignable to (i.e. is a subtype
of) a `D[Int ∨ String ∨ Double]`.

type ¬[A] = (() => A) => A
type ∨[T, U] = ¬[T] with ¬[U]
class D[-A](v: A) {
def get[T](f: (() => T)) = v match {
case x : ¬[T] => x(f)
}
}
def size(t: D[Int ∨ String]) = t match {
case x: D[¬[Int]] => x.get( () => 0 )
case x: D[¬[String]] => x.get( () => "" )
case x: D[¬[Double]] => x.get( () => 0.0 )
}
implicit def neg[A](x: A) = new D[¬[A]]( (f: (() => A)) => x )

scala> size(5)
res0: Any = 5

scala> size("")
error: type mismatch;
found : java.lang.String("")
required: D[?[Int,String]]
size("")
^

scala> size("hi" : D[¬[String]])
res2: Any = hi

scala> size(5.0 : D[¬[Double]])
error: type mismatch;
found : D[(() => Double) => Double]
required: D[?[Int,String]]
size(5.0 : D[?[Double]])
^

Apparently the Scala compiler has two bugs.

scala> class D[-A](v: A) {
def get[T](f: (() => T))(implicit e: A <:< ¬[T]) = v match {
case x : ¬[T] => x(f)
}
}
error: contravariant type A occurs in covariant position in
type <:<[A,(() => T) => T] of value e
def get[T](f: (() => T))(implicit e: A <:< ?[T]) = v
match {
^

1. It will not choose the correct implicit function for any type after
the first type in the destination disjunction.
2. It doesn't exclude the `D[¬[Double]]` case from the match.

The get method isn't constrained properly on input type, because the
compiler won't allow `A` in the covariant position. I think that is a
bug because all we want is evidence, we don't ever access the evidence
in the function? And I made the choice not to test for `case _` in the
`get` method, so I wouldn't have to unbox an `Option` in the `match`
in `size()`.

[1]: http://www.chuusai.com/2011/06/09/scala-union-types-curry-howard
[2]: http://www.chuusai.com/2011/06/09/scala-union-types-curry-howard/#comment-1160

[Paul Phillips]

On Fri, Feb 24, 2012 at 1:48 AM, Shelby <she...@coolpage.com> wrote:
>    scala> class D[-A](v: A) {
>      def get[T](f: (() => T))(implicit e: A <:< ¬[T]) = v match {
>        case x : ¬[T] => x(f)
>      }
>    }

You normally write that like

class D[-A](v: A) {

def get[T, A1 <: A](f: (() => T))(implicit e: A1 <:< ¬[T]) = v match {

case x : ¬[T] => x(f)
}
}

> The get method isn't constrained properly on input type, because the

> compiler won't allow `A` in the covariant position. I think that is a
> bug because all we want is evidence, we don't ever access the evidence
> in the function?

That doesn't matter. It's not a bug.

[Shelby]

> That doesn't matter.  It's not a bug.

Thanks for showing how to express what I wanted. I should have thought
of that, as I have used a related paradigm for turning off subsumption.
[1]

I was asking if it was a bug (in an overall sense of the Scala compiler
+library of what I wanted to express), because I thought there should
be a way to express what I wanted. I did realize the implementation of
implicits in the compiler is orthogonal to the user-land code for <:<,
so that is why I did not state it was a bug in the compiler.

[1] http://stackoverflow.com/questions/8360413/selectively-disable-subsumption-in-scala-correctly-type-list-contains

[Shelby]

On Feb 24, 5:48 pm, Shelby <she...@coolpage.com> wrote:
> Regarding comments 23 and 35 of [Mile Sabin's solution][5], here is a
> way to declare a union type at the use site...

The prior proposal needs an improvement. [Miles Sabin's solution][5]
worked correctly with subtyping.

type ¬[A] = A => Nothing

type ∨[T, U] = ¬[T] with ¬[U]

class Super
class Sub extends Super

scala> implicitly[(Super ∨ String) <:< ¬[Super]]
res0: <:<[?[Super,String],(Super) => Nothing] =

scala> implicitly[(Super ∨ String) <:< ¬[Sub]]
res2: <:<[?[Super,String],(Sub) => Nothing] =

scala> implicitly[(Super ∨ String) <:< ¬[Any]]
error: could not find implicit value for parameter
e: <:<[?[Super,String],(Any) => Nothing]
implicitly[(Super ? String) <:< ?[Any]]
^

My prior update's proposal (for near first-class union type) broke
subtyping.

scala> implicitly[D[¬[Sub]] <:< D[(Super ∨ String)]]
error: could not find implicit value for parameter
e: <:<[D[(() => Sub) => Sub],D[?[Super,String]]]
implicitly[D[?[Sub]] <:< D[(Super ? String)]]
^
The problem is that `A` in `(() => A) => A` appears in both the
covariant (return type) and contravariant (function input, or in this
case a return value of function which is a function input) positions,
thus substitutions can only be invariant.

Note that `A => Nothing` is necessary only because we want `A` in the
contravariant position, so that supertypes of `A` [are not subtypes]
[6] of `D[¬[A]]` nor `D[¬[A] with ¬[U]]` ([see also][7]). Since we
only need double contravariance, we can achieve equivalent to Miles'
solution even if we can discard the `¬` and `∨`.

trait D[-A]

scala> implicitly[D[D[Super]] <:< D[D[Super] with D[String]]]
res0: <:<[D[D[Super]],D[D[Super] with D[String]]] =

scala> implicitly[D[D[Sub]] <:< D[D[Super] with D[String]]]
res1: <:<[D[D[Sub]],D[D[Super] with D[String]]] =

scala> implicitly[D[D[Any]] <:< D[D[Super] with D[String]]]
error: could not find implicit value for parameter
e: <:<[D[D[Any]],D[D[Super] with D[String]]]
implicitly[D[D[Any]] <:< D[D[Super] with D[String]]]
^

So the complete fix is.

class D[-A] (v: A) {

def get[T <: A] = v match {

case x: T => x
}
}

implicit def neg[A](x: A) = new D[D[A]]( new D[A](x) )

def size(t: D[D[Int] with D[String]]) = t match {
case x: D[D[Int]] => x.get[D[Int]].get[Int]
case x: D[D[String]] => x.get[D[String]].get[String]
case x: D[D[Double]] => x.get[D[Double]].get[Double]
}

Note the prior 2 bugs in Scala remain, but the 3rd one is avoided as
`T` is now constrained to be subtype of `A`.

We can confirm the subtyping works.

def size(t: D[D[Super] with D[String]]) = t match {
case x: D[D[Super]] => x.get[D[Super]].get[Super]
case x: D[D[String]] => x.get[D[String]].get[String]
}

scala> size( new Super )
res7: Any = Super@1272e52

scala> size( new Sub )
res8: Any = Sub@1d941d7

I have been thinking that first-class intersection types are very
important, both for the [reasons Ceylon has them][8], and because
instead of [subsuming][9] to `Any` which means unboxing with a `match`
on expected types can generate a runtime error, the unboxing of a
([heterogeneous collection][10] containing a) disjunction can be type
checked (Scala has to fix the two bugs I noted). Unions are more
straightforward than the [complexity of using][11] the experimental
[HList][12] of [metascala][13] for heterogeneous collections.


[5]: http://www.chuusai.com/2011/06/09/scala-union-types-curry-howard
[6]: http://www.chuusai.com/2011/06/09/scala-union-types-curry-howard/#comment-1189
[7]: http://www.chuusai.com/2011/06/09/scala-union-types-curry-howard/#comment-54
[8]: http://ceylon-lang.org/documentation/1.0/faq/language-design/#optional_types
[9]: http://stackoverflow.com/questions/8360413/selectively-disable-subsumption-in-scala-correctly-type-list-contains
[10]: http://lambda-the-ultimate.org/node/4394#comment-68110
[11]: http://jnordenberg.blogspot.com/2008/08/hlist-in-scala.html
[12]: http://stackoverflow.com/questions/185972/arrays-in-scala/205729#205729
[13]: http://stackoverflow.com/questions/3508077/does-scala-have-type-disjunction-union-types/3508357#3508357

[Shelby]

Above implementation w.r.t. to De Morgan's laws:

http://groups.google.com/group/scala-language/browse_thread/thread/cfcf64dfff14e76f/637e214e6e6ceaf8?#637e214e6e6ceaf8