introduccion - ¿Cuáles son los problemas con una codificación ADT que asocia tipos con constructores de datos?(Como Scala.)

scala introduccion

Question

En Scala, los tipos de datos algebraicos se codifican como jerarquías sealed de tipo de un nivel. Ejemplo:

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

Con case class y case object , Scala genera un montón de cosas como equals , hashCode , unapply (usado por la coincidencia de patrones), etc. que nos trae muchas de las propiedades clave y características de los ADT tradicionales.

Sin embargo, hay una diferencia clave: en Scala, los "constructores de datos" tienen sus propios tipos . Compare los dos siguientes, por ejemplo (Copiado de los respectivos 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

Siempre consideré que la variación de Scala es ventajosa.

Después de todo, no hay pérdida de información de tipo . AppendIf[Int] por ejemplo es un subtipo de Positioning[Int] .

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

De hecho, obtienes un tiempo de compilación adicional invariable sobre el valor . (¿Podríamos llamar a esto una versión limitada del tipado dependiente?)

Esto puede ser de gran utilidad: una vez que sepa qué constructor de datos se utilizó para crear un valor, el tipo correspondiente se puede propagar a través del resto del flujo para agregar más seguridad de tipo. Por ejemplo, Play JSON, que usa esta codificación de Scala, solo le permitirá extraer fields de JsObject , no de cualquier JsValue arbitrario.

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

En Haskell, los fields probablemente tendrían el tipo JsValue -> Set (String, JsValue) . Lo que significa que fallará en el tiempo de ejecución para un JsArray etc. Este problema también se manifiesta en la forma de JsArray registros parciales bien conocidos.

La opinión de que el tratamiento de Scala de los constructores de datos es incorrecto se ha expresado en numerosas ocasiones : en Twitter, listas de correo, IRC, SO, etc. Desafortunadamente no tengo enlaces a ninguno de ellos, excepto a un par, esta respuesta de Travis Brown, y Argonaut , una biblioteca JSON puramente funcional para Scala.

Argonaut toma consciously el enfoque de Haskell (por clases de caso private y proporcionando constructores de datos manualmente). Puedes ver que el problema que mencioné con la codificación Haskell también existe con Argonaut. (Excepto que usa la Option para indicar parcialidad).

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

He estado reflexionando sobre esto durante bastante tiempo, pero todavía no entiendo qué es lo que hace que la codificación de Scala sea incorrecta. Claro que dificulta la inferencia tipo a veces, pero eso no parece ser una razón lo suficientemente fuerte para decretarlo mal. ¿Qué me estoy perdiendo?

Answer 1

Según mi leal saber y entender, hay dos razones por las que la codificación idiomática de las clases de casos de Scala puede ser mala: escriba inferencia y escriba especificidad. El primero es una cuestión de conveniencia sintáctica, mientras que el segundo es una cuestión de mayor alcance de razonamiento.

El problema de la subtipificación es relativamente fácil de ilustrar:

val x = Some(42)

El tipo de x resulta ser Some[Int] , Que probablemente no sea lo que usted quería. Puede generar problemas similares en otras áreas más problemáticas:

sealed trait ADT
case class Case1(x: Int) extends ADT
case class Case2(x: String) extends ADT
val xs = List(Case1(42), Case1(12))

El tipo de xs es List[Case1] . Esto básicamente garantiza que no es lo que quieres. Para evitar este problema, los contenedores como List deben ser covariantes en su parámetro de tipo. Desafortunadamente, la covarianza introduce una gran cantidad de problemas y, de hecho, degrada la solidez de ciertas construcciones (por ejemplo, Scalaz se compromete con su tipo de Monad y varios transformadores de mónada al permitir contenedores covariantes, a pesar de que no es correcto hacerlo).

Entonces, codificar ADT de esta manera tiene un efecto viral en tu código. No solo tiene que lidiar con la subtipificación en el ADT en sí, sino que cada contenedor que escriba debe tener en cuenta el hecho de que aterriza en subtipos de su ADT en momentos inoportunos.

La segunda razón para no codificar sus ADT usando clases de casos públicas es evitar saturar su espacio de tipo con "no tipos". Desde una cierta perspectiva, los casos de TDA no son realmente tipos: son datos. Si razonas sobre los ADT de esta manera (¡lo cual no está mal!), Tener tipos de primera clase para cada uno de tus casos de ADT aumenta el conjunto de cosas que debes tener en mente para razonar acerca de tu código.

Por ejemplo, considere el álgebra ADT desde arriba. Si quiere razonar sobre el código que utiliza este ADT, necesita estar constantemente pensando en "bueno, ¿y si este tipo es Case1 ?" Simplemente no es una pregunta que alguien realmente necesita hacer, ya que Case1 son datos. Es una etiqueta para un caso de coproducto en particular. Eso es todo.

Personalmente, no me importa mucho de ninguno de los anteriores. Quiero decir, los problemas de falta de solidez con la covarianza son reales, pero en general solo prefiero que mis contenedores sean invariables e instruir a mis usuarios a "chupar y anotar sus tipos". Es incómodo y es tonto, pero me parece preferible a la alternativa, que es una gran cantidad de pliegos repetitivos y constructores de datos "en minúsculas".

Como un comodín, una tercera desventaja potencial para este tipo de especificidad de tipo es que fomenta (o más bien, permite) un estilo más "orientado a objetos" en el que se colocan funciones específicas de cada caso en los tipos de ADT individuales. Creo que hay muy poca duda de que mezclar tus metáforas (clases de casos frente a polimorfismo de subtipo) de esta manera es una receta para el mal. Sin embargo, si este resultado es culpa de los casos tipeados es una pregunta abierta.