Khi nào cần đệ quy rõ ràng?

Question

Trong Haskell, nó là thành ngữ để viết càng nhiều mã của bạn trong các hàm bậc cao hơn như nếp gấp, bản đồ và mở ra càng tốt. Vậy những loại mã nào không thể được viết với những hàm bậc cao hơn? Khi nào đệ quy rõ ràng cần thiết?

Answer 1

Giả sử chúng tôi có ngôn ngữ không có đệ quy hoặc bất kỳ thứ gì giống như ngôn ngữ đó. Điều này có nghĩa là không có cấu trúc vòng lặp nào. Nó cũng có nghĩa là chúng ta có các loại (không đệ quy) để chúng ta không thể hình thành một bộ kết hợp Y và trốn thoát. Trong ngôn ngữ này, chúng tôi thực sự yếu, tách ra khỏi rất nhiều công cụ của chúng tôi.

Nhưng chúng tôi có thể đặt câu hỏi rất hay về ngôn ngữ này. Cụ thể, điều nhỏ nhất chúng ta phải đưa ra để nó trở nên mạnh mẽ như một ngôn ngữ không có những hạn chế như vậy là gì?

Hóa ra có hai câu trả lời.

1. Chúng tôi có thể giới thiệu chất kết dính đệ quy, giống như một lệnh let rec hoặc một cái gì đó giống như let Haskell mà luôn luôn là let rec. Nói cách khác, một cấu trúc cho phép chúng tôi xác định let x = e in b sao cho nếu x miễn phí trong e thì nó được tính như một điểm cố định trên phương trình x = e.

2. Chúng tôi có thể giới thiệu chức năng fix :: (a -> a) -> a sao cho fix f giảm trong một bước đến f (fix f).

Phải rõ ràng từ bản trình bày ở trên rằng fix có thể được triển khai bằng cách sử dụng các trình kết nối đệ quy. Có gì một chút ít rõ ràng là chất kết dính đệ quy có thể được thực hiện từ những phi đệ quy sử dụng sửa chữa, nhưng ở đây chúng tôi là:

let x = fix $ \this -> e 

Giá trị this đề cập đến toàn bộ biểu hiện mà kết thúc ràng buộc như x mà chỉ là những gì chúng tôi muốn.

---

Vậy tại sao tôi lại cố gắng nói tất cả những điều trên?

Về cơ bản, tôi muốn lập luận rằng không thể nói rằng đệ quy nhất thiết phải được thực hiện thông qua bộ kết hợp HOF như map miễn là bạn sẵn sàng xem xét fix trong danh sách đó. Tôi cũng muốn tranh luận rằng bất kỳ đệ quy nào được thực hiện bởi các combinators trong tập hợp đó có thể được thực hiện "một cách rõ ràng" bằng cách sử dụng các chất kết dính đệ quy. Chúng đều mạnh mẽ.

Phần thú vị có trong khi bạn xem xét các tổ hợp HOF như chính mình là foldr/unfoldr. Đây là những yếu tố kỹ thuật có phần là yếu hơn hơn fix/các chất kết dính đệ quy. Ưu điểm là nếu bạn xây dựng một ngôn ngữ lập trình chỉ với một bộ lựa chọn là foldr/unfoldr nguyên tắc giống như vậy thì bạn có thể nhận được một ngôn ngữ hoàn chỉnh rất phong phú, có thể là tổng số hoặc được đảm bảo chấm dứt.

Answer 2

Tôi nghĩ rằng rất nhiều người tìm thấy các định nghĩa dữ liệu đệ quy dễ đọc hơn các loại Mu/Fix/Nu. Nó không hoàn toàn cần thiết, nhưng rất hữu ích ở đó.

Tương tự, bạn sẽ viết các trường hợp Có thể gập lại/Mở ra cho một kiểu dữ liệu như vậy bằng cách sử dụng đệ quy, nhưng khi chúng được cung cấp, đệ quy rõ ràng là không bắt buộc.