Python'da yinelemeli veri türleri

Question

Python'da Haskell'deki özyinelemeli veri türlerine en yakın şey ne olabilir? (yani kendini tanımlarken türün kendi tanımını kullanmak.)

Düzenle:

Özyinelemeli türün daha somut bir tanımını vermek için, Haskell'de bir ikili ağaç aşağıdadır:

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

Bunu nasıl okuyorum şuna benziyor: İkili ağaç ya bir yaprak olabilir ya da yine ağaç türünün kendisi olan iki alt ağaç içerebilir.

Haskell'deki yinelemeli türler hakkında daha fazla bilgi için buraya başvurabilirsiniz: https://www.haskell.org/tutorial/goodies.html

Aslında aklımda olan, Haskell'deki bir kelime ağacı tanımını Python'a dönüştürmekti. Bu WordTreebenim eski bir projemin tanımı :

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

A WordTree, kelimelerin ortak öneklerinin ebeveynlerde saklandığı ve kalan kısımların ağaçların yaprağında sıralı bir şekilde depolandığı bir n-arytree yapısıdır. Bu tip tanımının bir Trie'ye biraz benzediğine inanıyorum. Yine de Haskell, işlevsel bir programlama dili olduğundan, bu tür tanımının özyinelemeli olmasına izin verir. Python'da (veya genel olarak nesne yönelimli programlamada) bu tür bir tür tanımına en yakın şey ne olabilir?

Answer 1

Python dinamik olarak yazıldığından, ihtiyacınız olan sınıfları tanımlamada herhangi bir sorun yoktur.

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

Bu tanımları yazmakla ilgileniyor olsanız bile, bunu diğer herhangi bir sınıf tabanlı nesne yönelimli dilde olduğu gibi yapabilirsiniz:

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

Türün adı için dizelerin kullanımına dikkat edin (daha yeni Python sürümlerinde kaçınabileceğiniz).

Doğrudan özyinelemeli cebirsel türler için mypy'deki bu açık konuya bakın:

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

---

WordTreeTanımladığınız şeyi tanımlamanın en yaygın (tavsiye edilmemekle birlikte) yolu bir üst sınıf ve sığ bir hiyerarşi kullanmaktır:

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]

Böyle bir uygulamayı kullanmak, isinstancekontrol kullanmayı gerektirebilir (ancak Python3.9, bunlar için size güzel bir şeker verir ). Dağınıklığı önlemek için bu örnekte oluşturucular ihmal edilmiştir; dataclassBunları ve diğer davranış türlerini kolayca elde etmek için kullanmak isteyebilirsiniz .

Bugüne kadar, Python size ilgisiz sınıfların miras almasına izin vermez WordTree, böylece bu tür programlar hakkında statik olarak mantık yürütme yeteneğinin bir kısmını ortadan kaldırır.

Scala ve Kotlin ve (yakında) Java gibi diğer bazı OOP dilleri, böyle bir tanımı ( sealedsınıfları kullanarak ) alabilir ve size Haskell gibi işlevsel diller tarafından verilenlere benzer tip kontrolleri ve sözdizimsel yapılar verebilir.

---

Tüm bildiğim için, bu tür bir tasarım genellikle yalnızca AST'ler gibi saf veri sınıfları için önerilir. Veri yapısının iç işleyişini açığa çıkardığından, trie gibi kullanıcıya dönük konteyneri tanımlamak için daha az uygundur. Dolayısıyla, bu tasarımla devam etseniz bile, onu bir uygulama ayrıntısı olarak kullanmak ve Trieiyi tanımlanmış bir API aracılığıyla istemci kodu tarafından kullanılacak başka bir sınıf kullanmak isteyebilirsiniz . Bu sınıfın bir WordTreealanı veya aynı mantığı uygulamanın başka bir yolu olabilir.

IMO Bu, nesne yönelimli tasarımın işlevsel tasarımdan farkı açısından çok önemlidir. İkincisi, veri akışına ve statik muhakemeye odaklanırken, ilki API'lere, genişletilebilirliğe ve ayrıştırmaya odaklanır. Bunun, diller ve ortamlar arasında taşınırken not edilmesinin yararlı olduğunu düşünüyorum - yukarıda belirtildiği gibi, bazı diller her iki tasarım yaklaşımını da etkinleştirmeye çalışır.