Tipe data rekursif dengan Python

Question

Apa hal di Python yang paling dekat dengan tipe data rekursif di Haskell? (yaitu menggunakan definisi tipe itu sendiri saat mendefinisikan dirinya sendiri.)

Edit:

Untuk memberikan definisi yang lebih konkret dari tipe rekursif, di bawah ini adalah pohon biner di Haskell:

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

Cara saya membacanya adalah seperti berikut ini: Pohon biner dapat berupa daun, atau dapat berisi dua sub-pohon yang juga merupakan jenis pohon itu sendiri.

Untuk informasi lebih lanjut tentang tipe rekursif di Haskell, Anda dapat merujuk ke sini: https://www.haskell.org/tutorial/goodies.html

Apa yang sebenarnya ada dalam pikiran saya adalah mengubah definisi pohon kata di Haskell ke Python. Ini adalah definisi dari WordTreeproyek lama saya:

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

A WordTreeadalah struktur pohon n-arytree di mana awalan kata yang umum disimpan di orang tua dan bagian yang tersisa disimpan di daun pohon dengan cara yang diurutkan. Saya percaya definisi tipe ini agak mirip dengan Trie. Namun, karena Haskell adalah bahasa pemrograman fungsional, ia memungkinkan definisi jenis ini menjadi rekursif. Apa hal yang paling dekat dengan Python (atau mungkin, dalam pemrograman berorientasi objek, secara umum) untuk jenis definisi tipe ini?

Answer 1

Karena Python diketik secara dinamis, tidak ada masalah dalam menentukan kelas apa pun yang Anda butuhkan.

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

Bahkan jika Anda tertarik untuk mengetik definisi ini, Anda dapat melakukannya seperti dalam bahasa berorientasi objek berbasis kelas lainnya:

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

Perhatikan penggunaan string untuk nama tipe (yang dapat Anda hindari di versi Python yang lebih baru).

Lihat masalah terbuka ini di mypy untuk tipe aljabar rekursif langsung seperti

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

---

Cara paling umum (meskipun tidak selalu direkomendasikan) untuk mendefinisikan yang WordTreeAnda gambarkan adalah menggunakan superclass dan hierarki yang dangkal:

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]

Menggunakan implementasi seperti itu mungkin memerlukan penggunaan isinstancepemeriksaan (meskipun Python3.9 memberi Anda gula yang bagus untuk itu). Konstruktor dihilangkan dalam contoh ini untuk menghindari kekacauan; Anda mungkin ingin menggunakannya dataclassuntuk mendapatkannya, dan jenis perilaku lainnya, dengan mudah.

Sampai saat ini, Python tidak memberi Anda cara untuk melarang kelas yang tidak terkait untuk mewarisi dari WordTree, sehingga melanggar beberapa kemampuan untuk alasan statis tentang program semacam itu.

Beberapa bahasa OOP lainnya, seperti Scala dan Kotlin dan (segera) Java , dapat mengambil definisi seperti itu (menggunakan sealedkelas ) dan memberi Anda pemeriksaan tipe dan konstruksi sintaksis yang mirip dengan yang diberikan oleh bahasa fungsional seperti Haskell.

---

Sejauh yang saya tahu, jenis desain ini biasanya direkomendasikan hanya untuk kelas data murni, seperti AST. Ini kurang cocok untuk mendefinisikan wadah yang menghadap pengguna seperti trie, karena memperlihatkan cara kerja bagian dalam struktur data. Jadi, meskipun Anda menggunakan desain itu, Anda mungkin ingin menggunakannya sebagai detail implementasi, dan menggunakan kelas lain Trie,, untuk digunakan oleh kode klien melalui API yang ditentukan dengan baik. Kelas itu dapat memiliki WordTreebidang, atau cara lain apa pun untuk mengimplementasikan logika yang sama.

IMO ini penting untuk bagaimana desain berorientasi objek berbeda dari desain fungsional. Yang terakhir berfokus pada aliran data dan penalaran statis, sedangkan yang pertama berfokus pada API, ekstensibilitas, dan decoupling. Saya rasa ini sangat membantu untuk diperhatikan, ketika melakukan porting antara bahasa dan lingkungan - meskipun seperti disebutkan di atas, beberapa bahasa mencoba mengaktifkan kedua pendekatan desain.