"Nổi" nghĩa là gì?

Question

Trên Haskell wiki I read that this:

fib = 
    let fib' 0 = 0 
     fib' 1 = 1 
     fib' n = fib (n - 1) + fib (n - 2) 
    in (map fib' [0 ..] !!) 

là hiệu quả hơn này:

fib x = 
    let fib' 0 = 0 
     fib' 1 = 1 
     fib' n = fib (n - 1) + fib (n - 2) 
    in map fib' [0 ..] !! x 

Bởi vì, "Trong trường hợp fib' thứ hai (lại) được xác định cho mỗi tham số x, do đó nó không thể được thả nổi. "

Tôi không hiểu ý nghĩa của điều này.

1. "Nổi" có nghĩa là gì? Làm cách nào để tối ưu hóa?
2. Tại sao fib' được định nghĩa lại cho mỗi yêu cầu fib?
3. Đây có phải là bản mở rộng eta hay không?

Answer 1

Đây không phải là lời giải thích tốt.

"nổi ra" chỉ có nghĩa rằng trong:

\x -> let y = ... in z 

nếu ... không đề cập đến x sau đó nó có thể được trôi ra của lambda:

let y = ... in \x -> z 

có nghĩa là nó sẽ chỉ được tính một lần, có thể tiết kiệm rất nhiều thời gian nếu ... là tốn kém. Tuy nhiên, GHC thận trọng về việc thực hiện tối ưu hóa như thế này, vì chúng có thể giới thiệu rò rỉ không gian. (Mặc dù nó không làm như vậy cho định nghĩa thứ hai nếu bạn cung cấp cho nó một chữ ký kiểu, như Daniel Fischer chỉ ra trong câu trả lời của mình.)

Đây không phải là về tối ưu hóa tự động, mặc dù. Đoạn đầu tiên xác định fib' bên ngoài lambda, trong khi thứ hai xác định nó bên trong (lambda là tiềm ẩn trong fib x = ..., tương đương với fib = \x -> ...), đó là những gì báo giá đang nói.

Tuy nhiên, điều đó không thực sự có liên quan; những gì có liên quan là trong đoạn đầu tiên, map fib' [0 ..] xảy ra bên ngoài lambda, và do đó kết quả của nó được chia sẻ giữa tất cả các ứng dụng của lambda (trong mã đó, "lambda" phát sinh từ ứng dụng một phần của (!!)). Trong phần sau, nó nằm bên trong lambda và rất có khả năng được tính toán lại cho mọi ứng dụng của fib.

Kết quả cuối cùng là việc triển khai trước đây lưu trữ các giá trị và hiệu quả hơn rất nhiều so với sau. Lưu ý rằng hiệu quả của đoạn đầu tiên phụ thuộc vào thực tế là fib' không recurse trực tiếp, nhưng thay vì thông qua fib, và do đó lợi ích từ các memoisation.

Nó liên quan đến việc mở rộng eta; đoạn mã thứ hai là phần mở rộng eta đầu tiên. Nhưng tuyên bố bạn trích dẫn không giải thích những gì đang xảy ra ở tất cả.

Lưu ý rằng đây là hành vi cụ thể của việc triển khai chứ không phải là một phần ngữ nghĩa của Haskell. Tuy nhiên, tất cả các triển khai hợp lý sẽ hoạt động theo cách này.

Answer 2

ehird 's câu trả lời giải thích những điều rất tốt, tuy nhiên có một điểm

Kết quả cuối cùng là thực hiện trước đây lưu trữ các giá trị và như vậy là xa hiệu quả hơn sau này.

đôi khi không đúng.

Nếu bạn biên dịch các module chứa hoặc sắc nét với optimisations (Tôi chỉ -O2, không -O1 kiểm tra, và tất nhiên chỉ GHC), có một số trường hợp để xem xét:

1. định nghĩa đầu tiên không có loại chữ ký
2. định nghĩa thứ hai với kiểu chữ ký fib :: Int -> Integer
3. định nghĩa đầu tiên với kiểu đa hình fib :: Num a => Int -> a
4. định nghĩa thứ hai không có loại chữ ký
5. định nghĩa thứ hai với kiểu chữ ký fib :: Num a => Int -> a

Trong trường hợp 1, hạn chế monomorphism sản xuất các loại fib :: Int -> Integer và danh sách map fib' [0 .. ] được chia sẻ trên tất cả các lời gọi của fib. Điều đó có nghĩa là nếu bạn từng truy vấn fib (10^6), bạn có một danh sách các số Fibonacci đầu tiên (1) trong bộ nhớ và nó sẽ chỉ được thu thập khi bộ thu gom rác có thể xác định nó không còn được sử dụng nữa. Đó thường là một rò rỉ bộ nhớ.

Trong trường hợp 2, kết quả (ing lõi) là thực tế giống hệt nhau đến trường hợp 1.

Trong trường hợp 4, danh sách không được chia sẻ qua lời gọi top-level khác nhau của fib (tất nhiên; kết quả có thể có nhiều loại, vì vậy sẽ có nhiều danh sách để chia sẻ), nhưng nó được khởi tạo một lần cho mỗi yêu cầu cấp cao nhất và được sử dụng lại cho các cuộc gọi từ fib', vì vậy việc tính toán fib n yêu cầu bổ sung O (n) và O (n^2) danh sách. Điều đó không quá tệ. Danh sách được thu thập khi tính toán hoàn tất, do đó không có rò rỉ không gian.

Trường hợp 3 thực tế giống hệt với 4.

Trường hợp 5, tuy nhiên, tệ hơn là đệ quy ngây thơ. Vì nó rõ ràng là đa hình và danh sách bị ràng buộc bên trong lambda, nên không thể sử dụng lại danh sách này cho các cuộc gọi đệ quy, mỗi cuộc gọi đệ quy sẽ tạo một danh sách mới ...