Dziwny <<loop>> wyjątek w generowaniu macierzy

Question

Wpadłem na problem nieskończonej pętli w Haskell i nie mogę zrozumieć, jaka jest przyczyna. Mam trzy wersje tego samego kodu poniżej. Pierwsza powoduje nieskończoną pętlę, podczas gdy dwie ostatnie nie. Jest to podstawowy wymyślony kod do generowania rekursywnie tablicy. W tym przypadku ma tylko trzy elementy, a jedyne wywołanie rekursywne dotyczy trzeciego elementu, który wybiera większą z dwóch pierwszych. Wydaje się, że instrukcja if a > b powoduje pętlę (ale później pokazuję, że nie może być przyczyną).

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) 

W poniższej wersji, po prostu użyć max a b zamiast rachunku if. Tu nie ma pętli.

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) 

W poniższej wersji trzymam if ale zip indeksy zamiast wrócić krotki z func. Ta również działa dobrze.

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 

tych dwóch pozostałych przypadkach wydają się wskazywać, że nie ma problemu z rekurencyjnej definicji lub wykorzystanie rachunku if.

Co to pozostawia jako przyczynę pętli?

Answer 1

Oto ciekawa obserwacja: w (i, max a b) wiemy (przed obliczaniem albo a lub b), że to krotka ma i w pierwszym składniku. Podobnie, w twoim kodzie zip możemy zauważyć, że pierwsze części krotek są 0, 1 ibez obliczania drugiej części krotek. Jednak w if a > b then (i, a) else (i, b), to nie oczywiste, że mamy krotka z i w pierwszej części: jeśli a > b jest dno, na przykład, to wynik tego wyrażenia jest dno, nie krotką z i w pierwszej części!

To ważne, ponieważ obliczanie a > b wymaga computing a, który wymaga Wiedząc, którego wartość jest w pozycji 0 w tablicy, która wymaga wiedząc, czy i jest 0 w ostatnim elementem odwzorowanym liście (a zatem powinien zastąpić poprzednią wartość 0) -- pętla.

Jedną z poprawek jest podniesienie części (i, _) z urządzenia if i użycie (i, if a > b then a else b). Zasadniczo to robi twoje rozwiązanie max.