如何定义"类型析取"(联合类型)？

Question

已经一个方法被提出来处理的重载方法双定义是,以取代与模式匹配超载:

object Bar {
   def foo(xs: Any*) = xs foreach { 
      case _:String => println("str")
      case _:Int => println("int")
      case _ => throw new UglyRuntimeException()
   }
}

这种方法要求我们放弃对参数的静态类型检查foo.能够写作会好得多

object Bar {
   def foo(xs: (String or Int)*) = xs foreach {
      case _: String => println("str")
      case _: Int => println("int")
   }
}

我可以接近Either,但它有两种以上的快速变得难看:

type or[L,R] = Either[L,R]

implicit def l2Or[L,R](l: L): L or R = Left(l)
implicit def r2Or[L,R](r: R): L or R = Right(r)

object Bar {
   def foo(xs: (String or Int)*) = xs foreach {
      case Left(l) => println("str")
      case Right(r) => println("int")
   }
}

它看起来像一个普通(优雅,高效的)解决方案将需要确定Either3,Either4....有谁知道一个替代的解决方案,以实现同样的目的吗？据我所知,Scala没有内置的"类型析取".另外,上面定义的隐式转换是否隐藏在某个标准库中,以便我可以导入它们？

Answer 1

Miles Sabin 通过Curry-Howard同构描述了一个非常好的方法来获得联盟类型在他最近的博客文章中Scala中的Unboxed union类型:

他首先将类型否定定义为

type ¬[A] = A => Nothing

使用De Morgan定律,这允许他定义联合类型

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

使用以下辅助构造

type ¬¬[A] = ¬[¬[A]]
type |?|[T, U] = { type ?[X] = ¬¬[X] <:< (T ? U) }

您可以按如下方式编写联合类型:

def size[T : (Int |?| String)#?](t : T) = t match {
    case i : Int => i
    case s : String => s.length
}

Answer 2

好吧,在具体的情况下Any*,这个技巧不起作用,因为它不接受混合类型.但是,由于混合类型也不能用于重载,这可能是你想要的.

首先,声明一个包含您希望接受的类的类,如下所示:

class StringOrInt[T]
object StringOrInt {
  implicit object IntWitness extends StringOrInt[Int]
  implicit object StringWitness extends StringOrInt[String]
}

接下来,声明foo如下:

object Bar {
  def foo[T: StringOrInt](x: T) = x match {
    case _: String => println("str")
    case _: Int => println("int")
  }
}

就是这样.你可以打电话foo(5)或foo("abc"),它会工作,但尝试foo(true)它会失败.这可以通过创建一个客户端代码来支持StringOrInt[Boolean],除非,如下面的Randall所说,你创建StringOrInt了一个sealed类.

它起作用,因为它T: StringOrInt意味着有一个类型的隐式参数StringOrInt[T],并且因为Scala在一个类型的伴随对象中查看是否存在implicits,以使代码要求该类型起作用.

Answer 3

Dotty是一个新的实验性Scala编译器,支持联合类型(书面A | B),因此您可以完全按照自己的意愿执行操作:

def foo(xs: (String | Int)*) = xs foreach {
   case _: String => println("str")
   case _: Int => println("int")
}

Answer 4

以下是Rex Kerr编码联合类型的方法.直接而简单!

scala> def f[A](a: A)(implicit ev: (Int with String) <:< A) = a match {
     |   case i: Int => i + 1
     |   case s: String => s.length
     | }
f: [A](a: A)(implicit ev: <:<[Int with String,A])Int

scala> f(3)
res0: Int = 4

scala> f("hello")
res1: Int = 5

scala> f(9.2)
<console>:9: error: Cannot prove that Int with String <:< Double.
       f(9.2)
        ^

来源: Miles Sabin 在这篇优秀博客文章中的评论#27,它提供了另一种在Scala中编码联合类型的方法.

Answer 5

可以将Daniel的解决方案概括如下:

sealed trait Or[A, B]

object Or {
   implicit def a2Or[A,B](a: A) = new Or[A, B] {}
   implicit def b2Or[A,B](b: B) = new Or[A, B] {}
}

object Bar {
   def foo[T <% String Or Int](x: T) = x match {
     case _: String => println("str")
     case _: Int => println("int")
   }
}

这种方法的主要缺点是

• 正如丹尼尔指出的那样,它不处理混合类型的集合/变量
• 如果匹配不详尽,编译器不会发出警告
• 如果匹配包含不可能的情况,编译器不会发出错误
• 像Either方法,进一步推广需要定义类似Or3,Or4等特点.当然,定义这些特征比定义相应的Either类要简单得多.

更新:

Mitch Blevins 展示 了一种非常类似的方法,并展示了如何将其概括为两种以上的类型,将其称为"口吃或".

Answer 6

通过结合类型列表的概念和Miles Sabin在这个领域的工作的简化,我有点偶然发现n-ary联合类型的相对干净的实现,有人在另一个答案中提到.

给定¬[-A]逆变的类型A,根据定义,A <: B我们可以编写 ¬[B] <: ¬[A],反转类型的排序.

给定类型A,B和X,我们想表达X <: A || X <: B.应用逆变,我们得到¬[A] <: ¬[X] || ¬[B] <: ¬[X].这又可以表示为¬[A] with ¬[B] <: ¬[X]其中一个A或B必须是超类型X或其X自身(考虑函数参数).

object Union {
  import scala.language.higherKinds

  sealed trait ¬[-A]

  sealed trait TSet {
    type Compound[A]
    type Map[F[_]] <: TSet
  }

  sealed trait ? extends TSet {
    type Compound[A] = A
    type Map[F[_]] = ? 
  }

  // Note that this type is left-associative for the sake of concision.
  sealed trait ?[T <: TSet, H] extends TSet {
    // Given a type of the form `? ? A ? B ? ...` and parameter `X`, we want to produce the type
    // `¬[A] with ¬[B] with ... <:< ¬[X]`.
    type Member[X] = T#Map[¬]#Compound[¬[H]] <:< ¬[X]

    // This could be generalized as a fold, but for concision we leave it as is.
    type Compound[A] = T#Compound[H with A]

    type Map[F[_]] = T#Map[F] ? F[H]
  }

  def foo[A : (? ? String ? Int ? List[Int])#Member](a: A): String = a match {
    case s: String => "String"
    case i: Int => "Int"
    case l: List[_] => "List[Int]"
  }

  foo(42)
  foo("bar")
  foo(List(1, 2, 3))
  foo(42d) // error
  foo[Any](???) // error
}

我确实花了一些时间尝试将这个想法与成员类型的上限结合起来,TList如harrah/up的s中所示,但是Map迄今为止,带有类型边界的实现具有挑战性.

Answer 7

使用implicits,类型类解决方案可能是最好的方法.这类似于Odersky/Spoon/Venners书中提到的monoid方法:

abstract class NameOf[T] {
  def get : String
}

implicit object NameOfStr extends NameOf[String] {
  def get = "str"
}

implicit object NameOfInt extends NameOf[Int] {
 def get = "int"
}

def printNameOf[T](t:T)(implicit name : NameOf[T]) = println(name.get)

如果你在REPL中运行它:

scala> printNameOf(1)
int

scala> printNameOf("sss")
str

scala> printNameOf(2.0f)
<console>:10: error: could not find implicit value for parameter nameOf: NameOf[
Float]
       printNameOf(2.0f)

              ^

Answer 8

我们想要一个类型操作符Or[U,V],可以用来约束类型参数X,或者使用X <: U或者X <: V.这是一个尽可能接近的定义:

trait Inv[-X]
type Or[U,T] = {
    type pf[X] = (Inv[U] with Inv[T]) <:< Inv[X]
}

以下是它的使用方法:

// use

class A; class B extends A; class C extends B

def foo[X : (B Or String)#pf] = {}

foo[B]      // OK
foo[C]      // OK
foo[String] // OK
foo[A]      // ERROR!
foo[Number] // ERROR!

这使用了一些Scala类型的技巧.主要是使用广义类型约束.给定类型U和V,Scala编译器提供一个名为U <:< V(和该类的隐式对象)的类,当且仅当Scala编译器可以证明它U是一个子类型V.这是一个使用通用类型约束的简单示例,适用于某些情况:

def foo[X](implicit ev : (B with String) <:< X) = {}

本实施例中的工作原理时X的类的一个实例B,一个String,或有一个类型既不是超类型,也不的子类型B或String.在前两种情况下,它被定义真正的with关键字(B with String) <: B和(B with String) <: String,所以斯卡拉将提供将作为传递一个隐含的对象ev:Scala编译器将正确接受foo[B]和foo[String].

在最后一种情况下,我依赖的事实是if U with V <: X,then U <: X或V <: X.这看起来很直观,我只是假设它.为什么当这个简单的例子失败这是一个从这个假设明确X是的超类型或亚型要么B或String:例如,在上面的例子中,foo[A]被错误地接受,foo[C]被错误地拒绝.再次,我们要的是某种类型的表达式中的变量U,V和X这是真的什么时候X <: U或X <: V.

斯卡拉的逆变概念在这里可以提供帮助.还记得这个特质trait Inv[-X]吗？因为它的类型参数是逆变的X,Inv[X] <: Inv[Y]当且仅当Y <: X.这意味着我们可以将上面的示例替换为实际可行的示例:

trait Inv[-X]
def foo[X](implicit ev : (Inv[B] with Inv[String]) <:< Inv[X]) = {}

这是因为表达式(Inv[U] with Inv[V]) <: Inv[X]是真的,通过上面的相同假设,恰好是时Inv[U] <: Inv[X]或者Inv[V] <: Inv[X],并且通过逆变的定义,这恰恰是当X <: U或时X <: V.

通过声明可参数化类型BOrString[X]并按如下方式使用它,可以使事情更加可重用:

trait Inv[-X]
type BOrString[X] = (Inv[B] with Inv[String]) <:< Inv[X]
def foo[X](implicit ev : BOrString[X]) = {}

斯卡拉现在将尝试构建类型BOrString[X]为每一个X该foo被调用,当类型将被精确构造X是无论是亚型B或String.这有效,并且有一个简写符号.下面的语法是等效的(除了ev现在必须在方法体中implicitly[BOrString[X]]而不是简单地引用ev)并且BOrString用作类型上下文绑定:

def foo[X : BOrString] = {}

我们真正喜欢的是一种创建类型上下文绑定的灵活方法.类型上下文必须是可参数化的类型,我们需要一种可参数化的方法来创建一个.这听起来像我们试图在类型上讨论函数,就像我们在值上调整函数一样.换句话说,我们喜欢以下内容:

type Or[U,T][X] = (Inv[U] with Inv[T]) <:< Inv[X]

这在Scala中是不可能直接实现的,但我们可以使用一个技巧来获得非常接近的技巧.这带给我们Or上面的定义:

trait Inv[-X]
type Or[U,T] = {
    type pf[X] = (Inv[U] with Inv[T]) <:< Inv[X]
}

这里我们使用结构类型和Scala的pound运算符来创建一个Or[U,T]保证有一个内部类型的结构类型.这是一个奇怪的野兽.要给出一些上下文,def bar[X <: { type Y = Int }](x : X) = {}必须使用其中定义AnyRef了类型的子类调用该函数Y:

bar(new AnyRef{ type Y = Int }) // works!

使用pound运算符允许我们引用内部类型Or[B, String]#pf,并使用类型运算符的中缀表示法Or,我们得出了我们的原始定义foo:

def foo[X : (B Or String)#pf] = {}

我们可以使用函数类型在其第一个类型参数中是逆变的事实,以避免定义特征Inv:

type Or[U,T] = {
    type pf[X] = ((U => _) with (T => _)) <:< (X => _)
} 

Answer 9

还有这个黑客:

implicit val x: Int = 0
def foo(a: List[Int])(implicit ignore: Int) { }

implicit val y = ""
def foo(a: List[String])(implicit ignore: String) { }

foo(1::2::Nil)
foo("a"::"b"::Nil)

请参阅解决类型擦除歧义(Scala).

Answer 10

您可以看看MetaScala,它有一些叫做的东西OneOf.我得到的印象是,这不适用于match语句,但您可以使用高阶函数模拟匹配.例如,看一下这个片段,但请注意"模拟匹配"部分已被注释掉,可能是因为它还没有完成.

现在进行一些编辑:我不认为有任何关于如你所描述的定义Either3,Either4等的令人震惊的事情.这基本上是Scala内置的标准22元组类型的双重选择.如果Scala有内置的析取类型,并且可能有一些很好的语法,那肯定会很好{x, y, z}.

Answer 11

我认为第一类不相交类型是一个密封的超类型,具有备用子类型,以及与所需类型的析取到这些备选子类型的隐式转换.

我假设这解决了Miles Sabin解决方案的注释 33-36,因此可以在使用站点使用的第一类类型,但我没有测试它.

sealed trait IntOrString
case class IntOfIntOrString( v:Int ) extends IntOrString
case class StringOfIntOrString( v:String ) extends IntOrString
implicit def IntToIntOfIntOrString( v:Int ) = new IntOfIntOrString(v)
implicit def StringToStringOfIntOrString( v:String ) = new StringOfIntOrString(v)

object Int {
   def unapply( t : IntOrString ) : Option[Int] = t match {
      case v : IntOfIntOrString => Some( v.v )
      case _ => None
   }
}

object String {
   def unapply( t : IntOrString ) : Option[String] = t match {
      case v : StringOfIntOrString => Some( v.v )
      case _ => None
   }
}

def size( t : IntOrString ) = t match {
    case Int(i) => i
    case String(s) => s.length
}

scala> size("test")
res0: Int = 4
scala> size(2)
res1: Int = 2

一个问题是Scala不会在大小写匹配上下文中使用,隐式转换IntOfIntOrString为Int(和StringOfIntOrStringto String),因此必须定义提取器并使用case Int(i)而不是case i : Int.

ADD:我在他的博客上回复了Miles Sabin如下.也许有几个改进:

1. 它扩展到超过2种类型,在使用或定义站点没有任何额外的噪音.
2. 参数被隐含地加框,例如不需要size(Left(2))或size(Right("test")).
3. 模式匹配的语法是隐式取消装箱的.
4. 装箱和拆箱可以通过JVM热点进行优化.
5. 语法可能是未来的第一类联合类型所采用的语法,因此迁移可能是无缝的？也许对于联合类型名称,最好使用V而不是Or,例如IntVString,` Int |v| String`,` Int or String`或我最喜欢的` Int|String`？

更新:对上述模式的析取进行逻辑否定,我在Miles Sabin的博客中添加了另一种(可能更有用)模式.

sealed trait `Int or String`
sealed trait `not an Int or String`
sealed trait `Int|String`[T,E]
case class `IntOf(Int|String)`( v:Int ) extends `Int|String`[Int,`Int or String`]
case class `StringOf(Int|String)`( v:String ) extends `Int|String`[String,`Int or String`]
case class `NotAn(Int|String)`[T]( v:T ) extends `Int|String`[T,`not an Int or String`]
implicit def `IntTo(IntOf(Int|String))`( v:Int ) = new `IntOf(Int|String)`(v)
implicit def `StringTo(StringOf(Int|String))`( v:String ) = new `StringOf(Int|String)`(v)
implicit def `AnyTo(NotAn(Int|String))`[T]( v:T ) = new `NotAn(Int|String)`[T](v)
def disjunction[T,E](x: `Int|String`[T,E])(implicit ev: E =:= `Int or String`) = x
def negationOfDisjunction[T,E](x: `Int|String`[T,E])(implicit ev: E =:= `not an Int or String`) = x

scala> disjunction(5)
res0: Int|String[Int,Int or String] = IntOf(Int|String)(5)

scala> disjunction("")
res1: Int|String[String,Int or String] = StringOf(Int|String)()

scala> disjunction(5.0)
error: could not find implicit value for parameter ev: =:=[not an Int or String,Int or String]
       disjunction(5.0)
                  ^

scala> negationOfDisjunction(5)
error: could not find implicit value for parameter ev: =:=[Int or String,not an Int or String]
       negationOfDisjunction(5)
                            ^

scala> negationOfDisjunction("")
error: could not find implicit value for parameter ev: =:=[Int or String,not an Int or String]
       negationOfDisjunction("")
                            ^
scala> negationOfDisjunction(5.0)
res5: Int|String[Double,not an Int or String] = NotAn(Int|String)(5.0)

另一个更新:关于Mile Sabin解决方案的评论23和35 ,这里有一种在使用站点声明联合类型的方法.注意它在第一级之后是未装箱的,即它具有可扩展到分离中的任何数量类型的优点,而Either需要嵌套装箱和我在先评论41中的范例是不可扩展的.换句话说,a D[Int ? String]可分配给(即,是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]])
                ^

显然Scala编译器有三个错误.

1. 在目标析取中的第一个类型之后,它不会为任何类型选择正确的隐式函数.
2. 它不排除D[¬[Double]]匹配的情况.

3.

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 {
                                           ^

get方法在输入类型上没有正确约束,因为编译器不允许A在协变位置.有人可能会认为这是一个错误,因为我们想要的只是证据,我们永远不会访问函数中的证据.我还是没有选择来测试case _的get方法,所以我不会有拆箱一Option中match的size().

2012年3月5日:之前的更新需要改进.Miles Sabin的解决方案适用于子类型.

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]]
                 ^

我之前更新的提议(近一流联盟类型)打破了子类型.

 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)]]
                 ^

问题在于,A在(() => A) => A协变(返回类型)和逆变(函数输入,或者在这种情况下是函数的返回值,函数输入)中出现的位置,因此替换只能是不变的.

请注意,A => Nothing是必要的,只是因为我们想A在逆变位置,这样的超类型A 不亚型的D[¬[A]]也不是D[¬[A] with ¬[U]](见).由于我们只需要双重逆变,即使我们可以丢弃¬和,我们也可以达到相当于Miles的解决方案?.

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]]]
                 ^

所以完整的解决方案是.

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]
}

请注意Scala中先前的2个错误仍然存​​在,但第3个错误被避免,因为T现在被限制为子类型A.

我们可以确认子类型的工作原理.

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

我一直在想,一流路口的类型是非常重要的,无论对于原因锡兰有他们,因为不是归并到Any这意味着拆箱与match预期的类型可以产生一个运行时错误,一个(的拆箱均质集合体含a)可以对类型进行拆分(Scala必须修复我记录的错误).工会比更直接使用的复杂实验HList的metascala异构集合.

Answer 12

如果您不喜欢Curry-Howard，还有另一种方法更容易理解：

type v[A,B] = Either[Option[A], Option[B]]

private def L[A,B](a: A): v[A,B] = Left(Some(a))
private def R[A,B](b: B): v[A,B] = Right(Some(b))  
// TODO: for more use scala macro to generate this for up to 22 types?
implicit def a2[A,B](a: A): v[A,B] = L(a)
implicit def b2[A,B](b: B): v[A,B] = R(b)
implicit def a3[A,B,C](a: A): v[v[A,B],C] = L(a2(a))
implicit def b3[A,B,C](b: B): v[v[A,B],C] = L(b2(b))
implicit def a4[A,B,C,D](a: A): v[v[v[A,B],C],D] = L(a3(a))
implicit def b4[A,B,C,D](b: B): v[v[v[A,B],C],D] = L(b3(b))    
implicit def a5[A,B,C,D,E](a: A): v[v[v[v[A,B],C],D],E] = L(a4(a))
implicit def b5[A,B,C,D,E](b: B): v[v[v[v[A,B],C],D],E] = L(b4(b))

type JsonPrimtives = (String v Int v Double)
type ValidJsonPrimitive[A] = A => JsonPrimtives

def test[A : ValidJsonPrimitive](x: A): A = x 

test("hi")
test(9)
// test(true)   // does not compile

我在第戎使用类似的技术