Haskell递归定义Data.Array与严格性的直觉理解及问题解析

原程序的行为差异 #

goodArray为何能正常输出 #

我们通过等式推理分析goodArray的求值过程：

goodArray = listArray (0, 1) (go 0)
where go x = x : go ((goodArray ! x) + 1)

Haskell的惰性求值策略会延迟计算直到必要时：

1. 当print goodArray触发数组构建时，listArray从go 0生成的无限列表中取前2个元素：
   • 数组0号元素：直接取go 0的头部0（已求值为弱头范式WHNF），无需后续递归。
   • 数组1号元素：取go ((goodArray!0)+1)的头部，此时这个表达式是未求值的thunk。
2. 当print需要输出1号元素时，才会求值该thunk：
   • 先计算goodArray!0，即已确定的0号元素0，得到0+1=1。
   • 调用go 1取其头部1作为1号元素的值（若你的运行结果显示为0，推测是代码笔误，比如go的递归部分未加1而是直接引用goodArray!x，但核心逻辑一致）。

整个过程没有循环依赖，所有求值步骤都能终止，因此goodArray可以正常输出。

badArray为何会卡住 #

badArray的差异仅在于go的参数是严格的（!x）：

badArray = listArray (0, 1) (go 0)
where go !x = x : go ((badArray ! x) + 1)

严格参数意味着调用go时必须先将参数求值到WHNF，这打破了惰性求值的循环终止条件：

1. 构建数组0号元素时，调用go 0：严格参数x=0被求值，返回0 : go ((badArray!0)+1)，0号元素正常存入数组。
2. 构建数组1号元素时，需要取go ((badArray!0)+1)的头部：
   • 由于go是严格参数，必须先求值((badArray!0)+1)。
   • 求值badArray!0需要访问badArray的0号元素，但此时badArray的整体结构仍在构建中（数组的1号元素尚未确定），GHC运行时会陷入循环等待，导致程序卡住。

数组维度改为(0,0)时的变化 #

当数组范围改为(0,0)时，listArray只需要取go 0的第一个元素0，无需触发后续的go ((badArray!0)+1)调用，因此不会产生循环依赖，badArray可以正常输出。

简化程序的行为差异 #

简化程序的定义如下：

goodArray = listArray (0, 1) [0, x] where x = goodArray!0
badArray = listArray (0, 1) [0, x] where !x = badArray!0

goodArray的正常行为 #

x是惰性绑定，数组1号元素存储的是x的thunk。当print求值1号元素时，x = goodArray!0会取已确定的0号元素0，因此正常输出。

badArray的卡住原因 #

!x是严格绑定，意味着badArray被求值时，必须先计算x的值：

• x = badArray!0需要访问badArray的0号元素，而badArray的构建依赖于x的值，形成了循环依赖：badArray的构建需要x，x的计算需要badArray，最终导致无限递归卡住。

维度改为(0,0)仍未定义的原因 #

即使数组范围改为(0,0)，badArray的where子句中!x = badArray!0是严格绑定，Haskell会在badArray的作用域内强制求值严格绑定的变量（即使x未被数组使用），因此仍会触发x = badArray!0的循环依赖，导致程序卡住。这和原程序的差异在于：原程序中严格参数的求值仅在需要生成数组元素时触发，而简化程序中严格绑定的x会在badArray初始化时就被强制求值。

内容的提问来源于stack exchange，提问作者Tarrasch