scala - 将类型与数据构造函数关联起来的 ADT 编码存在哪些问题？ (例如 Scala。)

Question

在 Scala 中，代数数据类型被编码为密封单级类型层次结构。示例:

-- Haskell
data Positioning a = Append
                   | AppendIf (a -> Bool)
                   | Explicit ([a] -> [a]) 

// Scala
sealed trait Positioning[A]
case object Append extends Positioning[Nothing]
case class AppendIf[A](condition: A => Boolean) extends Positioning[A]
case class Explicit[A](f: Seq[A] => Seq[A]) extends Positioning[A]

通过 case class 和 case object，Scala 生成了一堆东西，例如 equals、hashCode 、unapply(用于模式匹配)等为我们带来了传统 ADT 的许多关键属性和功能。

但有一个关键区别 - 在 Scala 中，“数据构造函数”有自己的类型。比较以下两个示例(从各自的 REPL 复制)。

// Scala

scala> :t Append
Append.type

scala> :t AppendIf[Int](Function const true)
AppendIf[Int]

-- Haskell

haskell> :t Append
Append :: Positioning a

haskell> :t AppendIf (const True)
AppendIf (const True) :: Positioning a

<小时/>

我一直认为 Scala 变体具有优势。

毕竟，不会丢失类型信息。例如，AppendIf[Int] 是 Positioning[Int] 的子类型。

scala> val subtypeProof = implicitly[AppendIf[Int] <:< Positioning[Int]]
subtypeProof: <:<[AppendIf[Int],Positioning[Int]] = <function1>

事实上，您会获得关于该值的额外编译时不变量。 (我们可以称之为依赖类型的有限版本吗？)

这可以得到很好的利用 - 一旦您知道使用什么数据构造函数来创建值，相应的类型就可以通过流程的其余部分传播，以增加更多的类型安全性。例如，使用此 Scala 编码的 Play JSON 只允许您从 JsObject 中提取 fields，而不是从任何任意 JsValue 中提取。

scala> import play.api.libs.json._
import play.api.libs.json._

scala> val obj = Json.obj("key" -> 3)
obj: play.api.libs.json.JsObject = {"key":3}

scala> obj.fields
res0: Seq[(String, play.api.libs.json.JsValue)] = ArrayBuffer((key,3))

scala> val arr = Json.arr(3, 4)
arr: play.api.libs.json.JsArray = [3,4]

scala> arr.fields
<console>:15: error: value fields is not a member of play.api.libs.json.JsArray
              arr.fields
                  ^

scala> val jsons = Set(obj, arr)
jsons: scala.collection.immutable.Set[Product with Serializable with play.api.libs.json.JsValue] = Set({"key":3}, [3,4])

在 Haskell 中，fields 可能具有类型 JsValue -> Set (String, JsValue)。这意味着 JsArray 等在运行时会失败。这个问题也以众所周知的部分记录访问器的形式表现出来。

Scala 对数据构造函数的处理方式是错误的观点已经被多次表达过 - 在 Twitter、邮件列表、IRC、SO 等上。不幸的是，除了适合情侣 - this answer作者:特拉维斯·布朗，和 Argonaut ，一个纯函数式的 Scala JSON 库。

阿尔戈英雄 consciously采用 Haskell 方法(通过私有(private)案例类，并手动提供数据构造函数)。您可以看到我提到的 Haskell 编码问题也存在于 Argonaut 中。 (除非它使用 Option 来表示偏爱。)

scala> import argonaut._, Argonaut._
import argonaut._
import Argonaut._

scala> val obj = Json.obj("k" := 3)
obj: argonaut.Json = {"k":3}

scala> obj.obj.map(_.toList)
res6: Option[List[(argonaut.Json.JsonField, argonaut.Json)]] = Some(List((k,3)))

scala> val arr = Json.array(jNumber(3), jNumber(4))
arr: argonaut.Json = [3,4]

scala> arr.obj.map(_.toList)
res7: Option[List[(argonaut.Json.JsonField, argonaut.Json)]] = None

我已经思考这个问题很长一段时间了，但仍然不明白是什么导致了 Scala 的编码错误。当然，它有时会妨碍类型推断，但这似乎并不是一个足够有力的理由来判定它是错误的。我错过了什么？

Answer 1

据我所知，Scala 的案例类惯用编码可能不好有两个原因:类型推断和类型特异性。前者是句法方便的问题，而后者是增加推理范围的问题。

子类型问题相对容易说明:

val x = Some(42)

x 的类型结果是 Some[Int]，这可能不是您想要的。您可能会在其他问题较多的领域产生类似的问题:

sealed trait ADT
case class Case1(x: Int) extends ADT
case class Case2(x: String) extends ADT

val xs = List(Case1(42), Case1(12))

xs的类型是List[Case1]。这基本上保证不是您想要的。为了解决这个问题，像 List 这样的容器需要在其类型参数中保持协变。不幸的是，协变引入了一大堆问题，并且实际上降低了某些构造的健全性(例如，Scalaz 通过允许协变容器来妥协其 Monad 类型和几个 monad 转换器，尽管事实上它是不健全的这样做)。

因此，以这种方式编码 ADT 会对您的代码产生一定程度的病毒式影响。您不仅需要处理 ADT 本身的子类型，而且您编写的每个容器都需要考虑到您在不合适的时刻登陆 ADT 的子类型这一事实。 p>

不使用公共(public)案例类对 ADT 进行编码的第二个原因是为了避免“非类型”使类型空间变得困惑。从某种角度来看，ADT 案例并不是真正的类型:它们是数据。如果您以这种方式推理 ADT(这并没有错!)，那么为每个 ADT 案例提供一流类型会增加您在推理代码时需要记住的事情。

例如，考虑上面的ADT代数。如果您想推理使用此 ADT 的代码，您需要不断思考“好吧，如果此类型是 Case1 怎么办？”这并不是任何人都需要问的问题，因为 Case1 是数据。它是特定联产品案例的标签。仅此而已。

就我个人而言，我不太关心上述任何一个。我的意思是，协方差的不健全问题是真实存在的，但我通常更喜欢让我的容器保持不变，并指示我的用户“接受它并注释你的类型”。它很不方便而且很愚蠢，但我发现它比替代方案更可取，替代方案是大量的样板折叠和“小写”数据构造函数。

作为通配符，这种类型特异性的第三个潜在缺点是它鼓励(或者更确切地说，允许)更加“面向对象”的风格，在这种风格中，您可以将特定于案例的函数放在各个 ADT 类型上。我认为毫无疑问，以这种方式混合你的隐喻(案例类与子类型多态性)会带来不好的结果。然而，这个结果是否是类型化案例的错误是一个悬而未决的问题。