Certains types de données algébriques permettent de résoudre facilement certains problèmes. Par exemple, un type de liste peut être exprimé de manière très succincte par:
data ConsList a = Empty | ConsCell a (ConsList a)
consmap f Empty = Empty
consmap f (ConsCell a b) = ConsCell (f a) (consmap f b)
l = ConsCell 1 (ConsCell 2 (ConsCell 3 Empty))
consmap (+1) l
Cet exemple particulier est en Haskell, mais il serait similaire dans d'autres langues avec une prise en charge native des types de données algébriques.
Il se trouve qu'il existe une correspondance évidente avec les sous-types de style OO: le type de données devient une classe de base abstraite et chaque constructeur de données devient une sous-classe concrète. Voici un exemple en Scala:
sealed abstract class ConsList[+T] {
def map[U](f: T => U): ConsList[U]
}
object Empty extends ConsList[Nothing] {
override def map[U](f: Nothing => U) = this
}
final class ConsCell[T](first: T, rest: ConsList[T]) extends ConsList[T] {
override def map[U](f: T => U) = new ConsCell(f(first), rest.map(f))
}
val l = (new ConsCell(1, new ConsCell(2, new ConsCell(3, Empty)))
l.map(1+)
La seule chose nécessaire au-delà des sous-classes naïves est un moyen de sceller les classes, c'est-à-dire de rendre impossible l'ajout de sous-classes à une hiérarchie.
Comment aborderiez-vous ce problème dans un langage comme C # ou Java? Les deux obstacles que j'ai trouvés en essayant d'utiliser des types de données algébriques en C # étaient les suivants:
- Je ne pouvais pas comprendre comment s'appelait le type du bas en C # (c'est-à-dire que je ne savais pas quoi mettre dans
class Empty : ConsList< ??? >
) - Je ne pouvais pas trouver un moyen de sceller
ConsList
afin qu'aucune sous-classe ne puisse être ajoutée à la hiérarchie
Quel serait le moyen le plus idiomatique d'implémenter les types de données algébriques en C # et / ou Java? Ou, si ce n'est pas possible, quel serait le remplacement idiomatique?
Réponses:
Il existe un moyen simple mais difficile de sceller les classes en Java. Vous mettez un constructeur privé dans la classe de base, puis créez des sous-classes de ses classes internes.
Pointage sur un modèle de visiteur pour l'envoi.
Mon projet jADT: Java Algebraic DataTypes génère pour vous tout ce que vous voulez. Https://github.com/JamesIry/jADT
la source
Either
. Voir ma questionVous pouvez y parvenir en utilisant le modèle de visiteur , qui complétera la correspondance de modèle. Par exemple
peut être écrit en Java comme
Le scellement est réalisé par la
Visitor
classe. Chacune de ses méthodes explique comment déconstruire l'une des sous-classes. Vous pouvez ajouter plusieurs sous - classes, mais il faudrait mettre en œuvreaccept
et en appelant une desvisit...
méthodes, il devrait soit se comporter commeCons
ou commeNil
.la source
Si vous abusez des paramètres nommés C # (introduits dans C # 4.0), vous pouvez créer des types de données algébriques faciles à faire correspondre:
Voici l'implémentation de la
Either
classe:la source
class Right<R> : Either<Bot,R>
:, où Soit est remplacé par une interface avec des paramètres de type covariant (sortant), et Bot est le type inférieur (sous-type de tous les autres types, à l'opposé de Object). Je ne pense pas que C # a un type de fond.En C #, vous ne pouvez pas avoir ce
Empty
type car, en raison de la réification, les types de base sont différents pour les différents types de membres. Vous pouvez seulement avoirEmpty<T>
; pas utile.En Java, vous pouvez avoir à
Empty : ConsList
cause de l'effacement de type, mais je ne suis pas sûr que le vérificateur de type ne crie pas quelque part.Cependant, étant donné que les deux langues ont
null
, vous pouvez penser à tous leurs types de référence comme étant "Quoi | Null". Donc, vous utiliseriez simplement lenull
comme "Vide" pour éviter d'avoir à spécifier ce qu'il dérive.la source
null
c’est qu’il est trop général: il représente l’absence de tout , c’est-à-dire le vide en général, mais je veux représenter l’absence d’éléments de liste, c’est-à-dire une liste vide en particulier. Une liste vide et un arbre vide doivent avoir des types distincts. De plus, la liste vide doit être une valeur réelle, car elle a toujours son propre comportement et doit donc avoir ses propres méthodes. Pour construire la liste[1, 2, 3]
, je veux direEmpty.prepend(3).prepend(2).prepend(1)
(ou dans un langage avec des opérateurs à droite associative1 :: 2 :: 3 :: Empty
), mais je ne peux pas direnull.prepend …
.Empty
et unEmpty<>
et l' abus des opérateurs de conversion implicites pour permettre une simulation assez pratique, si vous voulez. Vous utilisez essentiellementEmpty
du code, mais toutes les signatures de type, etc., n'utilisent que les variantes génériques.En Java, vous ne pouvez pas. Mais vous pouvez déclarer la classe de base comme étant un paquet privé, ce qui signifie que toutes les sous-classes directes doivent appartenir au même paquet que la classe de base. Si vous déclarez ensuite les sous-classes en tant que final, vous ne pourrez plus les sous-classer.
Je ne sais pas si cela réglerait votre problème réel cependant ...
la source
intanceof
vérifications dynamiques "pseudo-type-safe" (c'est-à-dire: je sais que c'est sûr, même si le compilateur ne le fait pas), simplement en m'assurant que vérifiez ces deux cas. Si, toutefois, quelqu'un d'autre ajoute une nouvelle sous-classe, je peux obtenir des erreurs d'exécution auxquelles je ne m'attendais pas.Le type de données
ConsList<A>
peut être représenté sous forme d'interface. L'interface expose une seuledeconstruct
méthode qui vous permet de "déconstruire" une valeur de ce type, c'est-à-dire de gérer chacun des constructeurs possibles. Les appels à unedeconstruct
méthode sont analogues à unecase of
forme en Haskell ou ML.La
deconstruct
méthode prend une fonction "callback" pour chaque constructeur de l'ADT. Dans notre cas, il faut une fonction pour le cas de liste vide et une autre pour le cas "cellule".Chaque fonction de rappel accepte comme arguments les valeurs acceptées par le constructeur. Donc, la casse "liste vide" ne prend pas d'argument, mais la casse "contre" prend deux arguments: la tête et la queue de la liste.
Nous pouvons coder ces "arguments multiples" en utilisant des
Tuple
classes ou en utilisant currying. Dans cet exemple, j'ai choisi d'utiliser unePair
classe simple .L'interface est implémentée une fois pour chaque constructeur. Premièrement, nous avons l'implémentation pour la "liste vide". L'
deconstruct
implémentation appelle simplement laemptyCase
fonction de rappel.Ensuite, nous implémentons le cas "cons cell" de manière similaire. Cette fois, la classe a des propriétés: la tête et la queue de la liste non vide. Dans l'
deconstruct
implémentation, ces propriétés sont transmises à laconsCase
fonction de rappel.Voici un exemple d'utilisation de ce codage ADTs: on peut écrire une
reduce
fonction qui est le facteur usuel sur les listes.Ceci est analogue à cette implémentation dans Haskell:
la source
Il n'y a pas de bonne façon de faire cela, mais si vous voulez vivre avec un bidouillage hideux, vous pouvez ajouter une vérification de type explicite au constructeur de la classe de base abstraite. En Java, ce serait quelque chose comme
En C #, c'est plus compliqué à cause des génériques réifiés - l'approche la plus simple pourrait être de convertir le type en chaîne et de le modifier.
Notez qu'en Java, même ce mécanisme peut théoriquement être contourné par quelqu'un qui le souhaite vraiment via le modèle de sérialisation ou
sun.misc.Unsafe
.la source
Type type = this.GetType(); if (type != typeof(Empty<T>) && type != typeof(ConsCell<T>)) throw new Exception();