Rekursive Datentypen in Python
Was könnte in Python den rekursiven Datentypen in Haskell am nächsten kommen? (dh die eigene Definition des Typs verwenden, während Sie sich selbst definieren.)
Bearbeiten:
Um eine konkretere Definition eines rekursiven Typs zu geben, finden Sie unten einen Binärbaum in Haskell:
data Tree a = Leaf a | Branch (Tree a) (Tree a)
Wie ich das lese, ist wie folgt: Ein Binärbaum kann entweder ein Blatt sein oder zwei Unterbäume enthalten, die wiederum der Typbaum selbst sind.
Weitere Informationen zu rekursiven Typen in Haskell finden Sie hier: https://www.haskell.org/tutorial/goodies.html
Was ich eigentlich vorhatte, war die Konvertierung einer Wortbaumdefinition in Haskell in Python. Dies ist die Definition von WordTreeaus einem alten Projekt von mir:
data WordTree = Word String | Subword String [WordTree] | Root [WordTree]
A WordTreeist eine n-Baumstruktur, bei der gemeinsame Präfixe von Wörtern bei den Eltern und verbleibende Teile sortiert am Blatt der Bäume gespeichert werden. Ich glaube, diese Typdefinition ähnelt einem Trie. Da Haskell jedoch eine funktionale Programmiersprache ist, kann diese Typdefinition rekursiv sein. Was könnte in Python (oder vielleicht in der objektorientierten Programmierung im Allgemeinen) für diese Art der Definition eines Typs am nächsten kommen?
Antworten
Da Python dynamisch typisiert wird, gibt es kein Problem beim Definieren der benötigten Klassen.
class Tree:
left = None
right = None
def __init__(self, left, right):
self.left = left
self.right = right
Selbst wenn Sie daran interessiert sind, diese Definitionen einzugeben, können Sie dies wie in jeder anderen klassenbasierten objektorientierten Sprache tun:
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
Beachten Sie die Verwendung von Zeichenfolgen für den Namen des Typs (die Sie in neueren Python-Versionen vermeiden können).
In dieser offenen Ausgabe in mypy finden Sie direkte rekursive algebraische Typen wie z
Tree = Union[Tuple['Tree', 'Tree'], int]
Die gebräuchlichste (wenn auch nicht unbedingt empfohlene) Art, das von WordTreeIhnen beschriebene zu definieren, ist die Verwendung einer Oberklasse und einer flachen Hierarchie:
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]
Die Verwendung einer solchen Implementierung erfordert möglicherweise die Verwendung von isinstanceÜberprüfungen (obwohl Python3.9 Ihnen für diese einen guten Zucker bietet ). Konstruktoren werden in diesem Beispiel weggelassen, um Unordnung zu vermeiden. Vielleicht möchten dataclassSie sie und andere Verhaltensweisen leicht verwenden.
Bis heute gibt es in Python keine Möglichkeit, das Erben nicht verwandter Klassen zu verbieten WordTree, wodurch ein Teil der Fähigkeit, statisch über solche Programme nachzudenken , beeinträchtigt wird.
Einige andere OOP-Sprachen wie Scala und Kotlin und (bald) Java können eine solche Definition (unter Verwendung von sealedKlassen ) annehmen und Ihnen Typprüfungen und syntaktische Konstrukte geben, die denen ähneln, die von funktionalen Sprachen wie Haskell angegeben werden.
Soweit ich weiß, wird diese Art von Design normalerweise nur für reine Datenklassen wie ASTs empfohlen. Es ist weniger geeignet, um benutzerbezogene Container wie trie zu definieren, da es das Innenleben der Datenstruktur offenlegt. Selbst wenn Sie sich für dieses Design entscheiden, möchten Sie es möglicherweise als Implementierungsdetail verwenden und eine andere Klasse verwenden, Triedie vom Clientcode über eine genau definierte API verwendet wird. Diese Klasse kann ein WordTreeFeld oder eine andere Möglichkeit haben, dieselbe Logik zu implementieren.
IMO ist dies wesentlich dafür, wie sich objektorientiertes Design von funktionalem Design unterscheidet. Letzteres konzentriert sich auf den Datenfluss und das statische Denken, während sich Ersteres auf APIs, Erweiterbarkeit und Entkopplung konzentriert. Ich denke, dies ist hilfreich zu beachten, wenn zwischen Sprachen und Umgebungen portiert wird - obwohl, wie oben erwähnt, einige Sprachen versuchen, beide Entwurfsansätze zu ermöglichen.