数组生成中的奇怪<< loop >>异常

Question

我遇到了Haskell中的无限循环问题,无法理解原因是什么.我在下面有三个版本的相同代码.第一个导致无限循环而后两个不导致.这是一些用于递归生成数组的基本设计代码.在这种情况下,它只有三个项目,唯一的递归调用是第三个项目,它选择前两个中较大的一个.该if a > b陈述似乎导致循环(但后来我表明它不是原因).

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)

在以下版本中,我只是使用max a b而不是if语句.这里没有循环.

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)

在接下来的版本中,我保留if,但zip该指数的,而不是返回从一个元组func.这个也运行良好.

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

这两个案例似乎表明递归定义或if语句的使用没有问题.

这会导致循环的原因是什么？

Answer 1

这是一个有趣的观察:在(i, max a b),我们知道(在计算之前a或之前b)这个元组i在其第一个组件中.同样,在你的zip代码中,我们可以观察到,元组的第一部分是0,1和2不计算元组的第二部分.然而,在if a > b then (i, a) else (i, b),它是不是很明显,我们有一个元组i在第一部分:如果a > b是底部,例如,那么这个表达式的结果是底部,而不是一个元组i在第一部分!

这很重要,因为计算a > b需要计算a,其需要知道哪些值在位置0阵列,其需要知道是否在i是0在所映射的列表的最后一个元素(并且因此应当覆盖以前的0值) -的环.

一个解决方法是将(i, _)部件从if中抬起,然后使用(i, if a > b then a else b).这基本上就是您的max解决方案所做的.