Types de données récursifs en Python
Quelle pourrait être la chose en Python qui est la plus proche des types de données récursifs dans Haskell? (c'est-à-dire en utilisant la propre définition du type tout en se définissant.)
Éditer:
Pour donner une définition plus concrète d'un type récursif, voici un arbre binaire en Haskell:
data Tree a = Leaf a | Branch (Tree a) (Tree a)
La façon dont je lis ceci est comme suit: Un arbre binaire peut soit être une feuille, soit contenir deux sous-arbres qui sont à nouveau l'arbre de types lui-même.
Pour plus d'informations sur les types récursifs dans Haskell, vous pouvez vous référer ici: https://www.haskell.org/tutorial/goodies.html
Ce que j'avais en fait à l'esprit était de convertir une définition d'arbre de mots dans Haskell en Python. Voici la définition du WordTreed'un ancien projet du mien:
data WordTree = Word String | Subword String [WordTree] | Root [WordTree]
A WordTreeest une structure à n-arbres dans laquelle les préfixes communs de mots sont stockés chez les parents et les parties restantes sont stockées à la feuille des arbres de manière triée. Je crois que cette définition de type est un peu similaire à un Trie. Pourtant, comme Haskell est un langage de programmation fonctionnel, il permet à cette définition de type d'être récursive. Quelle pourrait être la chose la plus proche en Python (ou peut-être, en programmation orientée objet, en général) pour ce type de définition d'un type?
Réponses
Étant donné que Python est typé dynamiquement, il n'y a aucun problème à définir les classes dont vous avez besoin.
class Tree:
left = None
right = None
def __init__(self, left, right):
self.left = left
self.right = right
Même si vous souhaitez taper ces définitions, vous pouvez le faire comme dans tout autre langage orienté objet basé sur les classes:
from typing import Union
class Tree:
left: Union['Tree', int]
right: Union['Tree', int]
def __init__(self, left: Union['Tree', int], right: Union['Tree', int]) -> None:
self.left = left
self.right = right
Notez l'utilisation de chaînes pour le nom du type (ce que vous pouvez éviter dans les versions Python plus récentes).
Voir ce problème ouvert dans mypy pour les types algébriques récursifs directs tels que
Tree = Union[Tuple['Tree', 'Tree'], int]
La manière la plus courante (mais pas nécessairement recommandée) de définir ce que WordTreevous décrivez consiste à utiliser une superclasse et une hiérarchie superficielle:
from typing import List, final
class WordTree: pass
@final
class Word(WordTree):
word: str
@final
class Subword(WordTree):
subword: str
children: List[WordTree]
@final
class Root(WordTree):
children: List[WordTree]
L'utilisation d'une telle implémentation peut nécessiter l'utilisation de isinstancevérifications (bien que Python3.9 vous donne du sucre pour ceux-ci). Les constructeurs sont omis dans cet exemple pour éviter l'encombrement; vous voudrez peut-être utiliser dataclasspour les obtenir, et d'autres types de comportement, facilement.
À ce jour, Python ne vous donne aucun moyen d'empêcher les classes non liées d'hériter de WordTree, ce qui brise une partie de la capacité de raisonner statiquement sur de tels programmes.
Certains autres langages POO, tels que Scala et Kotlin et (bientôt) Java , peuvent prendre une telle définition (en utilisant des sealedclasses ) et vous donner des vérifications de type et des constructions syntaxiques similaires à celles données par les langages fonctionnels tels que Haskell.
Pour autant que je sache, ce type de conception est généralement recommandé uniquement pour les classes de données pures, telles que les AST. Il est moins adapté pour définir un conteneur orienté utilisateur tel que trie, car il expose le fonctionnement interne de la structure de données. Ainsi, même si vous optez pour cette conception, vous voudrez peut-être l'utiliser comme détail d'implémentation et utiliser une autre classe,, Trieà utiliser par le code client via une API bien définie. Cette classe peut avoir un WordTreechamp ou tout autre moyen d'implémenter la même logique.
OMI, cela est essentiel pour comprendre en quoi la conception orientée objet diffère de la conception fonctionnelle. Le second se concentre sur le flux de données et sur le raisonnement statique, tandis que le premier se concentre sur les API, l'extensibilité et le découplage. Je pense que cela est utile à noter, lors du portage entre les langages et les environnements - bien que comme indiqué ci-dessus, certains langages essaient d'activer les deux approches de conception.