Non-pointfree phong cách là chậm hơn đáng kể

Question

Tôi có sau đây, câu nói cửa miệng mã cho việc tính toán số Fibonacci thứ n trong Haskell:

fibonacci :: Int -> Integer 
fibonacci = (map fib [0..] !!) 
    where fib 0 = 0 
      fib 1 = 1 
      fib n = fibonacci (n-2) + fibonacci (n-1) 

Sử dụng này, tôi có thể làm các cuộc gọi như:

ghci> fibonacci 1000 

và nhận câu trả lời gần như tức thời.

Tuy nhiên, nếu tôi sửa đổi các mã trên để nó không có trong phong cách pointfree, ví dụ:

fibonacci :: Int -> Integer 
fibonacci x = (map fib [0..] !!) x 
    where fib 0 = 0 
      fib 1 = 1 
      fib n = fibonacci (n-2) + fibonacci (n-1) 

nó là chậm hơn đáng kể. Trong phạm vi cuộc gọi như

ghci> fibonacci 1000 

treo cứng.

Sự hiểu biết của tôi là hai đoạn mã trên tương đương nhau, nhưng GHCi cầu xin sự khác biệt. Có ai có một lời giải thích cho hành vi này?

Answer 1

Để quan sát sự khác biệt, bạn có lẽ nên xem xét Core. Tôi đoán rằng đây nắm để so sánh (xấp xỉ)

let f = map fib [0..] in \x -> f !! x 

để

\x -> let f = map fib [0..] in f !! x 

Sau đó sẽ recompute f từ đầu trên tất cả các sự thỉnh nguyện. Trước đây không, hiệu quả bộ nhớ đệm cùng một f cho mỗi lời gọi.

Điều đó xảy ra trong trường hợp cụ thể này, GHC đã có thể tối ưu hóa thứ hai vào lần đầu tiên, khi tối ưu hóa được bật.

Lưu ý rằng GHC không phải lúc nào cũng thực hiện chuyển đổi này, vì đây không phải lúc nào cũng là tối ưu hóa. Bộ nhớ cache được sử dụng bởi lần đầu tiên được lưu giữ trong bộ nhớ mãi mãi. Điều này có thể dẫn đến lãng phí bộ nhớ, tùy thuộc vào chức năng trong tầm tay.

Answer 2

Tôi đã cố gắng tìm nó nhưng bị loại. Tôi nghĩ rằng tôi có nó trên máy tính của tôi ở nhà. Những gì tôi đọc là các chức năng sử dụng điểm cố định vốn đã nhanh hơn. Có nhiều lý do khác để sử dụng điểm cố định. Tôi gặp phải một trong văn bản chức năng Fibonacci lặp này. Tôi muốn xem làm thế nào một phiên bản lặp đi lặp lại sẽ thực hiện sau đó tôi nhận ra tôi đã không có cách nào sẵn sàng để đo lường. Tôi là một người da trắng Haskell. Nhưng đây là một phiên bản lặp lại cho ai đó để kiểm tra. Tôi không thể làm điều này để xác định trừ khi tôi sử dụng dấu chấm sau hàm cuối cùng đầu tiên. Tôi không thể giảm thêm nữa. tham số [0,1] được cố định và không được cung cấp dưới dạng giá trị tham số.

Prelude> fib = last . flip take (iterate (\ls -> ls ++ [last ls + last (init ls)]) [0,1]) 
Prelude> fib 25 

[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025]