Giải thích về “thắt nút”

Question

Khi đọc nội dung liên quan đến Haskell, đôi khi tôi thấy biểu hiện “buộc nút”, tôi nghĩ rằng tôi hiểu được là gì, nhưng không cách.

Vì vậy, có bất kỳ tốt, cơ bản, và đơn giản để hiểu giải thích về khái niệm này?

Answer 1

Ghép nút là giải pháp cho vấn đề cấu trúc dữ liệu hình tròn. Trong các ngôn ngữ bắt buộc bạn xây dựng một cấu trúc hình tròn bằng cách đầu tiên tạo ra một cấu trúc không hình tròn, và sau đó quay trở lại và sửa các con trỏ để thêm các vòng tròn.

Giả sử bạn muốn danh sách gồm hai phần tử có các phần tử "0" và "1". Có vẻ như không thể xây dựng được vì nếu bạn tạo nút "1" và sau đó tạo nút "0" để trỏ vào nó, bạn không thể quay lại và sửa nút "1" để trỏ trở lại nút "0" . Vì vậy, bạn có một tình huống gà-và-trứng, nơi cả hai nút cần phải tồn tại trước khi có thể được tạo ra.

Đây là cách bạn làm điều đó trong Haskell. Hãy xem xét giá trị sau:

alternates = x where 
    x = 0 : y 
    y = 1 : x 

Bằng ngôn ngữ không phải lười biếng, đây sẽ là vòng lặp vô hạn vì quá trình đệ quy không được hoàn thành. Nhưng trong đánh giá lười biếng của Haskell thì điều đúng: nó tạo ra một danh sách tròn hai phần tử.

Để xem cách hoạt động trong thực tế, hãy nghĩ về những gì xảy ra trong thời gian chạy. Việc thực hiện "thunk" thông thường của việc đánh giá lười biếng đại diện cho một biểu thức không được đánh giá là một cấu trúc dữ liệu chứa một con trỏ hàm cộng với các đối số được truyền cho hàm. Khi điều này được đánh giá, thunk được thay thế bằng giá trị thực để các tham chiếu trong tương lai không phải gọi lại hàm đó.

Khi bạn lấy phần tử đầu tiên của danh sách 'x' được đánh giá xuống giá trị (0, & y), trong đó bit "& y" là con trỏ đến giá trị của 'y'. Vì 'y' chưa được đánh giá, đây là một phần nhỏ. Khi bạn lấy phần tử thứ hai của danh sách, máy tính đi theo liên kết từ x đến thunk này và đánh giá nó. Nó đánh giá (1, & x), hoặc nói cách khác một con trỏ trở lại giá trị 'x' ban đầu. Vì vậy, bây giờ bạn có một danh sách tròn ngồi trong bộ nhớ. Lập trình viên không cần sửa chữa các con trỏ ngược vì cơ chế đánh giá lười biếng thực hiện nó cho bạn.

Answer 2

Nó không hoàn toàn là những gì bạn yêu cầu, và nó không liên quan trực tiếp đến Haskell, nhưng giấy của Bruce McAdam That About Wraps It Up đi sâu vào chủ đề này ở bề rộng và chiều sâu đáng kể. Ý tưởng cơ bản của Lý Tiểu Long là sử dụng toán tử kết hôn rõ ràng được gọi là WRAP thay vì ẩn ngụ liên kết được thực hiện tự động trong Haskell, OCaml và một số ngôn ngữ khác. Bài báo có rất nhiều ví dụ giải trí và nếu bạn quan tâm đến việc thắt nút, tôi nghĩ bạn sẽ có cảm giác tốt hơn cho quá trình này.