Đây có phải là hàm chuỗi Fibonacci đệ quy không?

Question

xem xét như sau (Haskell) mã:

fib=0:1:zipWith (+) fib (tail fib) 

Một đồng nghiệp đang cố gắng để khẳng định rằng đây không phải là một hàm đệ quy vì fib chỉ đơn giản là một danh sách định nghĩa riêng của mình với chính nó và đó là bằng cách nào đó khác với một hàm làm như vậy. Tôi nghĩ anh ấy đang hút thuốc.

Bạn nghĩ sao?

Answer 1

Định nghĩa fibonacci với zipWith không phải là hàm đệ quy, trên thực tế không có hàm liên quan, fib là danh sách (dữ liệu) được tự định nghĩa, sử dụng ngữ nghĩa lười của Haskell. Theo nghĩa nào đó, bạn có thể gọi nó là danh sách đệ quy hoặc dữ liệu đệ quy; nhưng không phải chức năng đệ quy. Bạn có thể khó khăn để quấn đầu quanh danh sách đệ quy vì rất ít ngôn ngữ lập trình có bất kỳ thứ gì gần gũi, nhưng bạn sẽ nhận thấy rằng trong Haskell, tất cả các hàm đều lấy chính xác một tham số. fib không nhận bất kỳ tham số nào vì nó không phải là một hàm. Vì không có hàm liên quan, bạn không thể có hàm đệ quy.

Đồng nghiệp của bạn không hút thuốc, anh ấy đã chứng ngộ (hoặc hút thuốc lá, nếu đó là định nghĩa của bạn về chứng ngộ).

Answer 2

Anh ấy đang bẻ khóa - chức năng trên rõ ràng là đệ quy.

Answer 3

Ví dụ bạn đã đưa ra là đệ quy. Nhưng chuỗi Fibonacci của tự nhiên không nhất thiết phải như vậy. Có iterative versions of the algorithm và thậm chí explicit functions.

Answer 4

Ngoài việc thực hiện Haskell ở đây, các số Fibonacci là một chuỗi được xác định bởi một mối quan hệ lặp lại. Về mặt toán học, mỗi thuật ngữ được định nghĩa là một hàm của các điều khoản trước đó. Đánh bại anh ta bằng ngữ nghĩa toán học.

Answer 5

Đó là đệ quy. Bạn có thể biết vì tên trên LHS của = cũng xuất hiện trên RHS.

Tuy nhiên, không một chức năng. Bạn có thể biết vì loại fib không chứa ->.

Answer 6

Vì đây là hàm đệ quy, cần phải có cả đệ quy và hàm. Như sepp2k chỉ ra, nó rõ ràng đệ quy vì tên fib xuất hiện trên cả hai mặt của =. Tức là, fib được định nghĩa theo chính nó.

Đây có phải là chức năng không? Không theo loại của nó. Trong haskell, chúng ta gọi hàm 0-argument là "data". Vì vậy, định nghĩa này của fib tạo ra một cấu trúc dữ liệu đệ quy, nhưng không phải là một hàm đệ quy.

Answer 7

Của tôi, tổ ong của những phân biệt thuật ngữ tinh tế. Cái gì thế này"?

fib=0:1:zipWith (+) fib (tail fib) 

Đây không phải là hàm đệ quy. Nó không phải là dữ liệu đệ quy. Nó là một định nghĩa đệ quy.

Điều gì đang được xác định?

fib 

Loại điều gì là fib, theo định nghĩa này?

[Integer] 

Danh sách số nguyên (hoặc có thể là danh sách bất kỳ công cụ số cũ nào).

Có phải là fib một hàm không? Không, đó là một danh sách. fib được xác định đệ quy? Vâng. fib có được xác định đệ quy nếu chúng tôi thay thế zipWith bằng một chức năng không phản hồi cùng loại (ví dụ: \ f xs ys -> xs)? Có, mặc dù nó sẽ là một danh sách được xác định đệ quy khác nhau.

Có phải là fib danh sách vòng tuần hoàn không? Không. "Cấu trúc dữ liệu đệ quy" có nghĩa là "cấu trúc dữ liệu tuần hoàn" không? Không theo giấy của Hoare, "Cấu trúc dữ liệu đệ quy": http://portal.acm.org/book_gateway.cfm?id=63445&type=pdf&bookpath=%2F70000%2F63445%2Fcb-p217-hoare.pdf&coll=&dl=&CFID=15151515&CFTOKEN=6184618

Trong cài đặt đã nhập, "cấu trúc dữ liệu đệ quy" nghĩa là không nhiều hoặc ít hơn "cư dân của loại được xác định đệ quy". Tương ứng "fred" là cấu trúc dữ liệu đệ quy, mặc dù nó không được xác định đệ quy, và thực sự nó có thể bị tác động bởi các hàm đệ quy như ++.

Cụm từ "hàm đệ quy" có nghĩa là "hàm được xác định đệ quy". Cụm từ "giá trị đệ quy" có nghĩa là "giá trị được xác định đệ quy", chẳng hạn như tồn tại trong các ngôn ngữ không nghiêm ngặt: các ngôn ngữ nghiêm ngặt có vấn đề "đệ quy giá trị".

Và nếu bạn nghĩ rằng đó là gàn dở, cố gắng xác định fib như vậy trong một tổng ngôn ngữ lập trình, và bạn sẽ khám phá ra rằng khái niệm "định nghĩa đệ quy" tách ra thành "định nghĩa bởi đệ quy cơ cấu" (tiêu thụ dữ liệu trong một cách dừng lại) và "định nghĩa bởi corecursion bảo vệ" (sản xuất dữ liệu theo cách mà đi), và rằng fib là của giống thứ hai. Trong cài đặt đó, năng suất của fib phụ thuộc rất lớn vào sự lười biếng của zipWith. Trong thiết lập Haskell, tất nhiên, bạn không cần phải lo lắng về bất kỳ công cụ nào để tìm ra loại định nghĩa gì đó, chỉ để tìm hiểu xem nó có một nửa cơ hội thực sự làm việc hay không.

Answer 8

Bởi vì hầu hết câu trả lời hỗ trợ đồng nghiệp của bạn liên quan đến các chức năng phần với: "fib là không một hàm đệ quy" Tôi muốn nói chi tiết về phần đệ quy Conor McBride đã gợi ý trong câu trả lời của anh ta.

Định nghĩa đưa ra cho fib là không đệ quy, nó là đồng đệ quy.

Co-đệ quy trông rất giống như đệ quy trong đó, như nhiều áp phích đã chỉ ra, LHS của định nghĩa xuất hiện trên RHS quá. Nhưng không có trường hợp cơ bản. Đệ quy và corecursion "chạy theo hướng ngược lại".

Định nghĩa trên của fib bắt đầu từ giá trị ban đầu 0 và 1 và di chuyển "lên" từ đó và tiếp tục. Mặt khác một định nghĩa đệ quy của, nói (một chức năng tính toán) số Fibonacci n-thứ

fib' 0 = 0 
fib' 1 = 1 
fib' n = fib' (n-1) + fib' (n-2) 

đi "xuống" từ số n-thứ cho đến khi nó đạt đến các trường hợp cơ sở và có dừng lại.

Tôi đoán đây vindicates các crackhead ở cả hai điểm :-)

---

Để đọc thêm kiểm tra bài viết trên wikipedia Corecursion và các liên kết đó. Nếu bạn có thể bắt tay vào nó, Chương 10 của Đường Haskell tới Logic, Toán học và Lập trình bởi Kees Doets và Jan van Eijck có thể đáng xem.

Answer 9

Mặc dù nhiều người trong nhận xét đang tranh cãi liệu định nghĩa có phải là một hàm hay không, nhưng mọi người dường như đồng ý rằng nó là đệ quy.

Đối với đối số chức năng/không có chức năng, trong Haskell, từ quan điểm của lập trình viên, CNTT KHÔNG CÓ VẤN ĐỀ! Bởi vì cả hai hàm và cấu trúc dữ liệu được đánh giá một cách lười biếng, một giá trị và một hàm không có đối số trả về một giá trị là không thể phân biệt được. Những gì bạn có là một danh sách các số nguyên, được đánh giá uể oải và đệ quy. fib đồng thời là "danh sách số nguyên", "hàm không có đối số trả về danh sách số nguyên", "danh sách hàm không có đối số trả về số nguyên" và "hàm không có đối số trả về danh sách hàm không có đối số trở về số nguyên ".

Nó thực sự không thành vấn đề. Ngôn ngữ không phân biệt giữa bốn. Loại lý thuyết không phân biệt giữa bốn (và vô số người khác: một hàm không có đối số trả về bất kỳ đối số nào có giá trị như nhau, như là một hàm không có đối số trả về, vô hạn quảng cáo). Nó thực sự làm cho không có sự khác biệt hay không bạn gọi fib một "chức năng" hay không.

Nhưng đó là đệ quy.