Các kiểu dữ liệu đệ quy trong Python

Sep 02 2020

Điều gì trong Python có thể là thứ gần nhất với các kiểu dữ liệu đệ quy trong Haskell? (nghĩa là sử dụng định nghĩa riêng của kiểu trong khi xác định chính nó.)

Biên tập:

Để đưa ra định nghĩa cụ thể hơn về kiểu đệ quy, dưới đây là cây nhị phân trong Haskell:

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

Cách tôi đọc nó giống như sau: Một cây nhị phân có thể là một chiếc lá hoặc có thể chứa hai cây con mà lại là cây loại.

Để biết thêm thông tin chi tiết về các kiểu đệ quy trong Haskell, bạn có thể tham khảo thêm tại đây: https://www.haskell.org/tutorial/goodies.html

Những gì tôi thực sự có trong đầu là chuyển đổi một định nghĩa cây từ trong Haskell sang Python. Đây là định nghĩa của WordTreetừ một dự án cũ của tôi:

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

A WordTreelà một cấu trúc n-arytree trong đó các tiền tố phổ biến của các từ được lưu trữ ở gốc và các phần còn lại được lưu trữ ở lá của cây theo cách được sắp xếp. Tôi tin rằng định nghĩa kiểu này hơi giống với Trie. Tuy nhiên, vì Haskell là một ngôn ngữ lập trình chức năng, nó cho phép định nghĩa kiểu này là đệ quy. Điều gì có thể là gần nhất trong Python (hoặc có thể, trong lập trình hướng đối tượng, nói chung) cho loại định nghĩa của một kiểu?

Trả lời

3 Elazar Sep 02 2020 at 03:19

Vì Python được nhập động nên không có vấn đề gì khi xác định bất kỳ lớp nào bạn cần.

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

Ngay cả khi bạn quan tâm đến việc nhập các định nghĩa này, bạn có thể làm điều đó giống như trong bất kỳ ngôn ngữ hướng đối tượng dựa trên lớp nào khác:

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

Lưu ý việc sử dụng các chuỗi cho tên của loại (mà bạn có thể tránh trong các phiên bản Python gần đây hơn).

Xem vấn đề mở này trong mypy để biết các loại đại số đệ quy trực tiếp như

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

Cách phổ biến nhất (mặc dù không nhất thiết được khuyến nghị) để xác định WordTreebạn mô tả là sử dụng lớp cha và hệ thống phân cấp nông:

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]

Việc sử dụng triển khai như vậy có thể yêu cầu sử dụng isinstancekiểm tra (mặc dù Python3.9 cung cấp cho bạn một đường tốt cho những điều đó). Các hàm tạo được bỏ qua trong ví dụ này để tránh lộn xộn; bạn có thể muốn sử dụng dataclassđể có được chúng và các loại hành vi khác một cách dễ dàng.

Cho đến nay, Python không cung cấp cho bạn cách nào để không cho phép các lớp không liên quan kế thừa từ WordTreeđó, do đó phá vỡ một số khả năng lập luận tĩnh về các chương trình như vậy.

Một số ngôn ngữ OOP khác, chẳng hạn như Scala và Kotlin và (sắp tới) Java , có thể định nghĩa như vậy (sử dụng sealedcác lớp ) và cung cấp cho bạn các kiểm tra kiểu và cấu trúc cú pháp tương tự như các cấu trúc được cung cấp bởi các ngôn ngữ chức năng như Haskell.

Đối với tất cả những gì tôi biết, loại thiết kế này thường chỉ được khuyến nghị cho các lớp dữ liệu thuần túy, chẳng hạn như AST. Nó ít phù hợp hơn để xác định vùng chứa hướng tới người dùng chẳng hạn như trie, vì nó cho thấy hoạt động bên trong của cấu trúc dữ liệu. Vì vậy, ngay cả khi bạn sử dụng thiết kế đó, bạn có thể muốn sử dụng nó như một chi tiết triển khai và sử dụng một lớp khác Trie, được mã khách hàng sử dụng thông qua một API được xác định rõ. Lớp đó có thể có một WordTreetrường hoặc bất kỳ cách nào khác để triển khai cùng một logic.

IMO đây là điều cần thiết để thiết kế hướng đối tượng khác với thiết kế chức năng như thế nào. Phần thứ hai tập trung vào luồng dữ liệu và lý luận tĩnh, trong khi phần thứ hai tập trung vào API, khả năng mở rộng và phân tách. Tôi nghĩ rằng điều này rất hữu ích cần lưu ý, khi chuyển giữa các ngôn ngữ và môi trường - mặc dù như đã nói ở trên, một số ngôn ngữ cố gắng kích hoạt cả hai phương pháp thiết kế.