Câu hỏi về nếp gấp và ngăn xếp ngăn xếp

Question

Tìm hiểu Bạn một Haskell nói về foldl' thay thế cho foldl vì dễ bị tràn ngăn xếp.

• Theo LYAH, foldl (+) 0 (replicate 1000000 1) nên ngăn xếp tràn, nhưng không có trên máy của tôi. Tại sao không? Thậm chí nếu tôi tăng số đó lên 10 triệu, nó không bị tràn. Nó chỉ mất rất nhiều bộ nhớ cho đến khi máy tính OS X của tôi trở nên không sử dụng được và tôi phải khởi động lại nó.
• Trong trường hợp nào tôi nên sử dụng foldl thay vì foldl'? Trong kinh nghiệm của tôi foldl' "chỉ hoạt động" trong khi foldl về cơ bản có thể sụp đổ máy tính của tôi (xem ở trên).
• Tôi không hiểu tại sao không có gì tương tự cho foldr. Tại sao không thể foldr tràn ngăn xếp và tại sao không có foldr'?

Answer 1

Nó không sụp đổ với ngăn xếp ngăn xếp vì ngăn xếp hiện được vô hạn theo mặc định. Nghĩa là, hành vi thời gian chạy GHC mặc định là cho phép ngăn xếp phát triển vô thời hạn - không có ràng buộc nào có thể kích hoạt lỗi tràn ngăn xếp.

https://ghc.haskell.org/trac/ghc/ticket/8189

Dưới đây là một mô tả cách hoạt động:

ngăn xếp Chủ đề (bao gồm cả ngăn xếp các chủ đề chính của) sống trên heap. Khi ngăn xếp phát triển, các khối ngăn xếp mới được thêm theo yêu cầu; nếu ngăn xếp co lại, các khối ngăn xếp bổ sung này được thu thập bởi bộ thu gom rác . Kích thước ngăn xếp ban đầu mặc định là nhỏ, theo thứ tự để giữ cho thời gian và chi phí không gian cho việc tạo luồng tới mức tối thiểu là và làm cho nó trở nên thực tế để tạo ra các luồng cho các tác phẩm nhỏ bé .

Answer 2

Tại sao không thể gập xếp chồng lên nhau và tại sao không có nếp gấp '?

Vâng, foldr không phải là đệ quy đuôi, tức là nó không gọi trực tiếp vào bản thân:

foldr f a (x:xs) = f x (foldr f a xs) 

Sau foldr giảm, điều khiển đi đến người dùng cung cấp f. Do đó, không cần phải có một số foldr' để buộc các đối số trước khi chuyển chúng đến f: nếu điều đó được mong muốn, người gọi chỉ có thể vượt qua một số f nghiêm ngặt (ví dụ: khai thác các mẫu kiểu bang hoặc seq).

Cho dù nó tràn ngăn xếp phụ thuộc vào những gì f thực hiện. Ví dụ:

f x y = x 

sẽ khiến danh sách chỉ được truy cập trong phần tử đầu tiên. Ngược lại,

f x y = seq y x 

có thể gây tràn bộ nhớ (hoặc hành vi sử dụng bộ nhớ).Thay vào đó,

f x y = x+1 : y 

sẽ khiến danh sách đầu ra được tạo ra một cách lười biếng, tương tự như map (+1) xs, mà không có bất ngờ khó chịu.

Khi @dfeuer chỉ ra, có tồn tại Data.Foldable.foldr' hoạt động trên bất kỳ Foldable nào dưới dạng vòng lặp đúng nghiêm ngặt. Trên danh sách, đó là khá nhiều dự phòng, như đã thảo luận ở trên. Trên các loại Foldable khác, thay vào đó nó có thể có ý nghĩa.