Tại sao thành ngữ đệ quy trong Haskell "'n + 1' và 'n'" và không phải là "'n' và 'n-1'"?

Question

Tôi đang làm việc cách của mình thông qua cuốn sách Haskell Graham Hutton, và trong chương đệ quy của mình, ông thường mô-trận đấu trên "n + 1", như trong:

myReplicate1 0 _ = [] 
myReplicate1 (n+1) x = x : myReplicate1 n x 

Tại sao điều đó và không phải là sau đây, (1) có vẻ giống hệt nhau về mặt chức năng và (2) trực quan hơn về sự hiểu biết những gì đang xảy ra với đệ quy:

myReplicate2 0 _ = [] 
myReplicate2 n x = x : myReplicate2 (n-1) x 

có cái gì tôi đang thiếu ở đây? Hay nó chỉ là vấn đề về phong cách?

Answer 1

Đó là các mẫu n + k (cần tránh!) Trong hàm đầu tiên. Cả hai hàm đều làm điều tương tự, ngoại trừ n + k không khớp với số âm. Tuy nhiên, tùy chọn thứ hai được đề nghị, và có thể được áp dụng nếu bạn không muốn có số âm theo mục đích, vì các mẫu n + k được loại bỏ là removed anyways.

Vì vậy, không, bạn đang bỏ lỡ không có gì, và nó thực sự là một vấn đề về phong cách, nhưng tôi hiếm khi thấy các mẫu n + k trong tự nhiên.

Answer 2

mẫu n + k chỉ khớp khi n> = 0. Vì vậy, trong myReplicate1, mẫu n + 1 sẽ chỉ khớp với các số dương và một số n âm sẽ gây ra một ngoại lệ mẫu không cần thiết. Trong myReplicate2, n âm sẽ tạo một danh sách vô hạn.

Vì vậy, nói cách khác bạn có thể sử dụng mẫu n + k khi bạn không muốn mẫu khớp với số âm, nhưng việc sử dụng bảo vệ thay thế sẽ rõ ràng hơn.

Answer 3

myReplicate n x = take n (repeat x) 

Xong và hoàn tất. : D

Answer 4

Mẫu N + K cũng có những hàm ý nghiêm ngặt khác nhau.

Ví dụ:

f (n+1) = Just n 
g n = Just (n-1) 

f là nghiêm ngặt về số đầu tiên của nó, g thì không. Điều này không có gì đặc biệt với các mẫu n + k nhưng áp dụng cho tất cả các mẫu.

Answer 5

Tôi nghĩ rằng ý tưởng đằng sau nó là thế này: Chúng ta có thể định nghĩa một (chậm) loại kiểu số tự nhiên như thế này:

data Natural = Zero | S Integer 

Vì vậy 0 == Zero, 1 == S Zero và vân vân.

Khi bạn làm điều này, nó trở nên tự nhiên để sử dụng mô hình kết hợp như thế này:

myReplicate1 Zero _ = [] 
myReplicate1 (S n) x = x : myReplicate1 n x 

tôi nghĩ (và nó chỉ là một phỏng đoán) mà ý tưởng đằng sau n+1 mẫu là nó giống như một phiên bản nhanh về những gì Tôi vừa mô tả. Vì vậy, n+1 được cho là giống như mẫu S n. Vì vậy, nếu bạn đang suy nghĩ theo cách này, các mẫu n+1 có vẻ tự nhiên.

Điều này cũng làm rõ lý do tại sao chúng tôi có điều kiện bên là n>=0. Chúng tôi chỉ có thể đại diện cho n>=0 bằng cách sử dụng loại Natural.