gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-03 05:29:37 25 4
gpt4 key购买 nike

在 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 classcase object,Scala 生成了一堆东西,例如 equalshashCodeunapply(用于模式匹配)等为我们带来了传统 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 的编码错误。当然,它有时会妨碍类型推断,但这似乎并不是一个足够有力的理由来判定它是错误的。我错过了什么?

最佳答案

据我所知,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 类型上。我认为毫无疑问,以这种方式混合你的隐喻(案例类与子类型多态性)会带来不好的结果。然而,这个结果是否是类型化案例的错误是一个悬而未决的问题。

关于scala - 将类型与数据构造函数关联起来的 ADT 编码存在哪些问题? (例如 Scala。),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25330359/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com