Haskell: lặp lại một hàm số lần lớn mà không cần stackoverflow

Question

Là một newbie cho Haskell tôi đang cố gắng lặp lại một hàm (ví dụ, bản đồ hậu cần) một số lượng lớn lần. Trong một ngôn ngữ bắt buộc này sẽ là một vòng lặp đơn giản, tuy nhiên trong Haskell tôi kết thúc với tràn ngăn xếp. Lấy ví dụ mã này:

main = print $ iter 1000000 

f x = 4.0*x*(1.0-x) 

iter :: Int -> Double 
iter 0 = 0.3 
iter n = f $ iter (n-1) 

Đối với một số lượng nhỏ các lần lặp mã hoạt động, nhưng đối với một triệu lần lặp tôi nhận được một tràn ngăn xếp không gian:

Stack space overflow: current size 8388608 bytes. 
Use `+RTS -Ksize -RTS' to increase it. 

Tôi không thể hiểu tại sao điều này xảy ra. Việc đệ quy đuôi nên được tốt ở đây. Có thể vấn đề là đánh giá lười biếng. Tôi đã thử nghiệm một số cách để đánh giá nghiêm ngặt, bằng cách chèn $! hoặc seq ở các vị trí khác nhau, nhưng không thành công.

Cách nào để Haskell lặp lại chức năng một số lượng lớn thời gian?

Tôi đã thử các đề xuất từ ​​các bài đăng có liên quan: here hoặc here, nhưng tôi luôn kết thúc với luồng lưu lượng truy cập cho một số lượng lớn các lần lặp lại, ví dụ: main = print $ iterate f 0.3 !! 1000000.

Answer 1

Vấn đề là định nghĩa của bạn

iter :: Int -> Double 
iter 0 = 0.3 
iter n = f $ iter (n-1) 

cố gắng để đánh giá theo hướng sai. Mở ra nó trong một vài bước, chúng tôi có được

iter n = f (iter (n-1)) 
     = f (f (iter (n-2))) 
     = f (f (f (iter (n-3)))) 
     ... 

và toàn bộ cuộc gọi chồng iter 1000000-iter 0 phải được xây dựng trước khi bất cứ điều gì có thể được đánh giá. Nó sẽ là như nhau trong một ngôn ngữ nghiêm ngặt. Bạn phải tổ chức nó để một phần của việc đánh giá có thể diễn ra trước khi định kỳ. Cách thông thường là phải có một tham số tích lũy, như

iter n = go n 0.3 
    where 
    go 0 x = x 
    go k x = go (k-1) (f x) 

Sau đó, thêm chú thích nghiêm khắc - trong trường hợp trình biên dịch không đã thêm chúng - sẽ làm cho nó chạy trơn tru mà không cần tốn nhiều stack.

Biến thể iterate có cùng vấn đề với số iter của bạn, chỉ ngăn xếp cuộc gọi được xây dựng từ trong ra ngoài chứ không phải bên ngoài như của bạn. Nhưng kể từ iterate xây dựng cuộc gọi stack của nó bên trong ra, một phiên bản chặt chẽ hơn của iterate (hoặc một mô hình tiêu thụ nơi lặp trước đó buộc trước đó) giải quyết vấn đề,

iterate' :: (a -> a) -> a -> [a] 
iterate' f x = x `seq` (x : iterate' f (f x)) 

tính toán iterate' f 0.3 !! 1000000 mà không vấn đề.