Tại sao phiên bản 'khắc phục' này hiệu quả hơn trong Haskell?

Question

Trong Haskell, đây là một đơn giản (ngây thơ) định nghĩa của một điểm cố định

fix :: (a -> a) -> a 
fix f = f (fix f) 

Nhưng, đây là cách Haskell thực sự thực hiện nó (hiệu quả hơn)

fix f = let x = f x in x 

Câu hỏi của tôi là tại sao là thứ hai hiệu quả hơn cái đầu tiên?

Answer 1

Làm chậm fix gọi f trên mỗi bước đệ quy, trong khi gọi nhanh f chính xác một lần. Nó có thể được hình dung với tracing:

import Debug.Trace 

fix f = f (fix f) 
fix' f = let x = f x in x 

facf :: (Int -> Int) -> Int -> Int 
facf f 0 = 1 
facf f n = n * f (n - 1) 

tracedFacf x = trace "called" facf x 

fac = fix tracedFacf 
fac' = fix' tracedFacf 

Bây giờ thử một số hoạt động:

> fac 3 
called 
called 
called 
called 
6 
> fac' 3 
called 
6 

Cụ thể hơn, let x = f x in x kết quả trong một thunk lười biếng được phân bổ cho x, và một con trỏ đến thunk này sẽ được chuyển cho f. Khi đánh giá lần đầu tiên fix' f, đoạn thunk được đánh giá và tất cả các tham chiếu đến nó (cụ thể là: cái chúng tôi chuyển đến f) được chuyển hướng đến giá trị kết quả. Nó chỉ xảy ra rằng x được cung cấp một giá trị cũng chứa tham chiếu đến x.

Tôi thừa nhận điều này có thể khá khó khăn. Đó là điều mà một người nên quen với khi làm việc với sự lười biếng.

Answer 2

Tôi tin rằng điều này đã được yêu cầu, nhưng tôi không thể tìm thấy câu trả lời. Lý do là phiên bản đầu tiên

fix f = f (fix f) 

là một hàm đệ quy, do đó, nó không thể được gạch chân và sau đó được tối ưu hóa. Từ GHC manual:

Ví dụ, đối với một chức năng tự đệ quy, các máy cắt vòng lặp có thể chỉ là chức năng riêng của mình, vì vậy một pragma INLINE luôn bỏ qua.

Nhưng

fix f = let x = f x in x 

là không đệ quy, đệ quy được chuyển vào các ràng buộc let, vì vậy nó có thể inline nó.

Cập nhật: Tôi đã thực hiện một số thử nghiệm và trong khi phiên bản cũ không trực tuyến trong khi phiên bản thứ hai không có vẻ quan trọng đối với hiệu suất. Vì vậy, các giải thích khác (một đối tượng duy nhất trên heap vs tạo ra một lần lặp) dường như chính xác hơn.

Answer 3

Tôi không nghĩ rằng điều này luôn luôn (hoặc nhất thiết phải bao giờ) giúp khi bạn gọi fix với một hàm lấy hai đối số để tạo một hàm lấy một đối số. Bạn sẽ phải chạy một số điểm chuẩn để xem. Nhưng bạn cũng có thể gọi nó bằng một hàm lấy một đối số!

fix (1 :) 

là danh sách liên kết tròn.Sử dụng định nghĩa ngây thơ của fix, thay vào đó nó sẽ là một danh sách vô hạn, với những phần mới được xây dựng uể oải khi cấu trúc bị ép buộc.