Lạ <<loop>> ngoại lệ trong thế hệ Array

Question

Tôi gặp phải vấn đề vòng lặp vô hạn trong Haskell và không thể hiểu nguyên nhân là gì. Tôi có ba phiên bản của cùng một mã bên dưới. Việc đầu tiên gây ra một vòng lặp vô hạn trong khi hai sau không. Đây là một số mã cơ bản giả tạo để tạo ra một mảng đệ quy. Trong trường hợp này, nó chỉ có ba mục và cuộc gọi đệ quy duy nhất là cho mục thứ ba chọn lớn hơn của hai mục đầu tiên. Tuyên bố if a > b dường như gây ra một vòng lặp (nhưng sau đó tôi cho thấy rằng nó không thể là nguyên nhân).

import Data.Array 

main :: IO() 
main = print grid 
    where grid = array (0, 2) $ map func [0 .. 2] 
     func i 
      | i == 2 = let a = grid ! (i - 1) 
          b = grid ! (i - 2) 
         in if a > b 
           then (i, a) 
           else (i, b) 
      | otherwise = (i, 0) 

Trong phiên bản tiếp theo, tôi chỉ đơn giản sử dụng max a b thay vì báo cáo kết quả if. Không có vòng lặp ở đây.

main :: IO() 
main = print grid 
    where grid = array (0, 2) $ map func [0 .. 2] 
     func i 
      | i == 2 = let a = grid ! (i - 1) 
          b = grid ! (i - 2) 
         in (i, max a b) 
      | otherwise = (i, 0) 

Trong phiên bản sau, tôi giữ if nhưng zip các chỉ số thay vì trả lại một tuple từ func. Điều này cũng chạy tốt.

main :: IO() 
main = print grid 
    where grid = array (0, 2) $ zip [0 .. 2] $ map func [0 .. 2] 
     func i 
      | i == 2 = let a = grid ! (i - 1) 
          b = grid ! (i - 2) 
         in if a > b 
           then a 
           else b 
      | otherwise = 0 

Hai trường hợp khác dường như cho thấy không có vấn đề với định nghĩa đệ quy hoặc sử dụng câu lệnh if.

Điều gì xảy ra với tư cách là nguyên nhân của vòng lặp?

Answer 1

Dưới đây là một quan sát thú vị: trong (i, max a b), chúng tôi biết (trước khi tính toán a hoặc b) rằng tuple này có i trong thành phần đầu tiên của nó. Tương tự, trong mã số zip của bạn, chúng tôi có thể quan sát thấy các phần đầu tiên của bộ dữ liệu là 0, 1 và 2 mà không cần tính toán phần thứ hai của bộ dữ liệu. Tuy nhiên, trong if a > b then (i, a) else (i, b), nó là không phải là hiển nhiên rằng chúng tôi có một tuple với i ở phần đầu tiên: nếu a > b ở dưới cùng, ví dụ, kết quả của biểu thức này ở dưới cùng, không phải là một tuple với i ở phần đầu tiên!

này quan trọng vì tính a > b đòi hỏi tính toán a, đòi hỏi hiểu biết mà giá trị ở vị trí 0 trong mảng, mà đòi hỏi phải biết liệu i là 0 trong yếu tố cuối cùng của danh sách ánh xạ (và do đó nên ghi đè lên giá trị 0 trước) -- một vòng lặp.

Một khắc phục là nâng phần (i, _) ra khỏi if và sử dụng (i, if a > b then a else b). Đây thực chất là giải pháp max của bạn.