Quels sont les problèmes d'un codage ADT qui associe les types aux constructeurs de données ? (Comme Scala).

Question

En Scala, les types de données algébriques sont codés sous forme de sealed les hiérarchies de types à un niveau. Exemple :

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

Avec case class es et case object Scala génère un tas de choses comme equals , hashCode , unapply (utilisé pour le filtrage), etc. qui nous apporte un grand nombre de propriétés et de caractéristiques clés des ADT traditionnelles.

Il y a cependant une différence essentielle - En Scala, les "constructeurs de données" ont leurs propres types. . Comparez les deux exemples suivants (copiés des REPLs respectifs).

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

---

J'ai toujours considéré que la variante Scala était du côté des avantages.

Après tout, il n'y a pas de perte d'informations sur le type . AppendIf[Int] par exemple, est un sous-type de Positioning[Int] .

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

En fait, vous obtenez un invariant supplémentaire en temps de compilation concernant la valeur . (Pourrait-on appeler cela une version limitée du typage dépendant ?)

Cela peut être utilisé à bon escient - Une fois que vous savez quel constructeur de données a été utilisé pour créer une valeur, le type correspondant peut être propagé à travers le reste du flux pour ajouter plus de sécurité de type. Par exemple, Play JSON, qui utilise cet encodage Scala, vous permettra seulement d'extraire fields de JsObject et non d'un quelconque arbitraire 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])

En Haskell, fields aurait probablement le type JsValue -> Set (String, JsValue) . Ce qui signifie qu'il échouera au moment de l'exécution pour une JsArray etc. Ce problème se manifeste également sous la forme des accesseurs d'enregistrements partiels bien connus.

L'opinion selon laquelle le traitement des constructeurs de données par Scala est erroné a été exprimée à de nombreuses reprises. - sur Twitter, les listes de diffusion, IRC, SO etc. Malheureusement, je n'ai pas de liens vers aucun d'entre eux, à l'exception de quelques-uns cette réponse par Travis Brown, et Argonaute une bibliothèque JSON purement fonctionnelle pour Scala.

Argonaute consciemment adopte l'approche Haskell (par private les classes de cas, et la fourniture manuelle de constructeurs de données). Vous pouvez voir que le problème que j'ai mentionné avec l'encodage Haskell existe aussi avec Argonaut. (Sauf qu'il utilise Option pour indiquer la partialité).

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

J'ai réfléchi à cette question pendant un certain temps, mais je ne comprends toujours pas pourquoi l'encodage de Scala est incorrect. Bien sûr, il entrave parfois l'inférence de type, mais cela ne semble pas être une raison suffisante pour le décréter mauvais. Qu'est-ce qui m'échappe ?

Answer 1

À ma connaissance, il y a deux raisons pour lesquelles l'encodage idiomatique des classes de cas dans Scala peut être mauvais : l'inférence de type et la spécificité de type. La première est une question de commodité syntaxique, tandis que la seconde est une question de portée accrue du raisonnement.

Le problème du sous-typage est relativement facile à illustrer :

val x = Some(42)

Le type de x s'avère être Some[Int] ce qui n'est probablement pas ce que vous vouliez. Vous pouvez générer des problèmes similaires dans d'autres domaines plus problématiques :

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

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

Le type de xs est List[Case1] . Il s'agit essentiellement garanti pour ne pas être ce que vous voulez. Afin de contourner ce problème, des conteneurs tels que List doivent être covariants dans leur paramètre de type. Malheureusement, la covariance introduit tout un tas de problèmes, et dégrade en fait la solidité de certaines constructions (par exemple, Scalaz fait des compromis sur ses paramètres de type). Monad et plusieurs transformateurs de monades en autorisant les conteneurs covariants, malgré le fait qu'il ne soit pas sain de le faire).

Ainsi, l'encodage des ADT de cette manière a un effet quelque peu viral sur votre code. Non seulement vous devez traiter le sous-typage dans l'ADT lui-même, mais aussi chaque Le conteneur que vous écrivez doit prendre en compte le fait que vous atterrissez sur des sous-types de votre ADT à des moments inopportuns.

La deuxième raison de ne pas coder vos ADT en utilisant des classes de cas publiques est d'éviter d'encombrer votre espace de type avec des "non-types". D'un certain point de vue, les cas ADT ne sont pas vraiment des types : ce sont des données. Si vous raisonnez sur les ADTs de cette manière (ce qui n'est pas faux !), alors avoir des types de première classe pour chacun de vos cas ADT augmente l'ensemble des choses que vous devez avoir à l'esprit pour raisonner sur votre code.

Par exemple, considérez le ADT l'algèbre du dessus. Si vous voulez raisonner sur du code qui utilise cette ADT, vous devez constamment penser à "et si ce type était Case1 ?" C'est juste une question que personne ne se pose vraiment besoins à demander, puisque Case1 est une donnée. C'est une étiquette pour un cas particulier de coproduit. C'est tout.

Personnellement, je ne me soucie guère de tout ce qui précède. Je veux dire, les problèmes de non-sens avec la covariance sont réels, mais je préfère généralement rendre mes conteneurs invariants et dire à mes utilisateurs de "faire avec et d'annoter vos types". C'est peu pratique et c'est stupide, mais je trouve cela préférable à l'alternative, qui est un tas de plis passe-partout et de constructeurs de données en "minuscules".

En tant que joker, un troisième inconvénient potentiel de ce type de spécificité de type est qu'il encourage (ou plutôt, permet) un style plus "orienté objet" où vous mettez des fonctions spécifiques aux cas sur les types ADT individuels. Je pense qu'il y a très peu de doute que mélanger vos métaphores (classes de cas contre polymorphisme de sous-type) de cette façon est une recette pour le mal. Cependant, que ce résultat soit ou non la faute des cas typés est une question ouverte.