Trình bày nội bộ danh sách Haskell?

Question

Haskell hỗ trợ một số thao tác cơ bản để đệ quy thông qua danh sách, như head, tail, init và last. Tôi tự hỏi, nội bộ, Haskell đại diện cho dữ liệu danh sách của nó như thế nào? Nếu đó là danh sách được liên kết đơn lẻ, thì các hoạt động init và last có thể trở nên tốn kém khi danh sách tăng lên. Nếu đó là danh sách được liên kết kép, tất cả bốn hoạt động có thể được thực hiện O(1) khá dễ dàng, mặc dù chi phí của một số bộ nhớ. Dù bằng cách nào, điều quan trọng là tôi phải biết, vì vậy tôi có thể viết mã thích hợp. (mặc dù, các đặc tính của lập trình chức năng có vẻ là một trong những "hỏi những gì nó làm, không phải như thế nào nó").

Answer 1

Danh sách được trình bày dưới dạng ... danh sách được liên kết đơn lẻ. Định nghĩa được cho bởi:

data [] a = [] | a : [a] 

mà bạn có thể viết như sau:

data List a = Empty | Cons a (List a) 

Cách bố trí bộ nhớ được hoàn toàn xác định bởi đây.

• Constructors là đống phân bổ
• lĩnh vực đa hình nội bộ là con trỏ đến nút phân bổ khác
• Cột sống là lười biếng

Vì vậy, bạn kết thúc với một cái gì đó như thế này:

Vì vậy, head là O (1) trên cấu trúc này, trong khi last hoặc (++) là O (n)

Không có phép thuật để cấu trúc dữ liệu trong Haskell - nét thẳng về phía trước của họ làm hoàn toàn rõ ràng những gì mức độ phức tạp sẽ được (modulo lười biếng). Nếu bạn cần sự phức tạp khác nhau, hãy sử dụng một cấu trúc khác (chẳng hạn như IntMap, Trình tự, HashMap, Vector v.v.) ...

Answer 2

danh sách Haskell đang đơn lẻ liên kết, vì vậy cons, head và tail là O (1) trong khi init và last là O (n ).

Nếu bạn cần hiệu suất tốt hơn, hãy cân nhắc sử dụng loại Seq từ Data.Sequence, cung cấp truy cập O (1) cho cả hai đầu của danh sách. Bên trong nó sử dụng 2-3 finger trees.