Tipi di dati ricorsivi in ​​Python

Question

Quale potrebbe essere la cosa in Python che è più vicina ai tipi di dati ricorsivi in ​​Haskell? (ovvero utilizzando la definizione del tipo durante la definizione di se stesso.)

Modificare:

Per dare una definizione più concreta di un tipo ricorsivo, di seguito è riportato un albero binario in Haskell:

data Tree a             = Leaf a | Branch (Tree a) (Tree a) 

Il modo in cui leggo questo è il seguente: un albero binario può essere una foglia o può contenere due sottoalberi che sono di nuovo l'albero dei tipi stesso.

Per ulteriori informazioni sui tipi ricorsivi in ​​Haskell, puoi fare riferimento a qui: https://www.haskell.org/tutorial/goodies.html

Quello che avevo in mente era convertire una definizione di albero di parole in Haskell in Python. Questa è la definizione di WordTreeda un mio vecchio progetto:

data WordTree = Word String | Subword String [WordTree] | Root [WordTree]

A WordTreeè una struttura ad albero in cui i prefissi comuni di parole sono memorizzati nei genitori e le parti rimanenti sono immagazzinate sulla foglia degli alberi in modo ordinato. Credo che questa definizione di tipo sia in qualche modo simile a un Trie. Tuttavia, poiché Haskell è un linguaggio di programmazione funzionale, consente a questa definizione di tipo di essere ricorsiva. Quale potrebbe essere la cosa più vicina in Python (o forse, nella programmazione orientata agli oggetti, in generale) per questo tipo di definizione di un tipo?

Answer 1

Poiché Python è tipizzato dinamicamente, non ci sono problemi a definire le classi di cui hai bisogno.

class Tree:
    left = None
    right = None
    def __init__(self, left, right):
        self.left = left
        self.right = right

Anche se sei interessato a digitare queste definizioni, puoi farlo come in qualsiasi altro linguaggio orientato agli oggetti basato su classi:

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

Nota l'uso di stringhe per il nome del tipo (che puoi evitare nelle versioni più recenti di Python).

Vedi questo problema aperto in mypy per i tipi algebrici ricorsivi diretti come

Tree = Union[Tuple['Tree', 'Tree'], int]

---

Il modo più comune (anche se non necessariamente consigliato) di definire ciò WordTreeche descrivi è usare una superclasse e una gerarchia superficiale:

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'utilizzo di una simile implementazione potrebbe richiedere l'uso di isinstancecontrolli (sebbene Python3.9 ti dia un bel zucchero per quelli). I costruttori vengono omessi in questo esempio per evitare il disordine; potresti volerlo utilizzare dataclassper ottenerli e altri tipi di comportamento, facilmente.

Ad oggi, Python non offre alcun modo per impedire a classi non correlate di ereditare da WordTree, interrompendo così parte della capacità di ragionare staticamente su tali programmi.

Alcuni altri linguaggi OOP, come Scala e Kotlin e (presto) Java , possono prendere tale definizione (usando sealedclassi ) e darti controlli di tipo e costrutti sintattici simili a quelli forniti da linguaggi funzionali come Haskell.

---

Per quanto ne so, questo tipo di progettazione è generalmente consigliato solo per classi di dati puri, come gli AST. È meno adatto per definire un contenitore rivolto all'utente come trie, poiché espone il funzionamento interno della struttura dei dati. Quindi, anche se segui quel progetto, potresti volerlo utilizzare come dettaglio di implementazione e utilizzare un'altra classe, Trieda utilizzare dal codice client attraverso un'API ben definita. Quella classe può avere un WordTreecampo o qualsiasi altro modo per implementare la stessa logica.

IMO questo è essenziale per come il design orientato agli oggetti differisce dal design funzionale. Il secondo si concentra sul flusso di dati e sul ragionamento statico, mentre il primo si concentra su API, estensibilità e disaccoppiamento. Penso che questo sia utile da notare, quando si esegue il porting tra lingue e ambienti, sebbene, come notato sopra, alcuni linguaggi tentano di abilitare entrambi gli approcci di progettazione.