Haskell 的 halve 为何会提前求值整个列表？

2026-11-04数据小陈

结论

问题出在 mapFst 对递归结果进行模式匹配。为了返回 mapFst 处理后的元组，Haskell 必须先求值 go xs ys，直到得到一个元组。这会让递归一路走到基例。因此，虽然元组字段本身是惰性的，这段实现仍会在构造当前结果的第一半时先遍历到列表末尾。

可以让 go 直接构造结果元组，并用惰性的 let 模式绑定递归结果：

halve :: [a] -> ([a], [a])
halve xs = go xs xs
  where
    go (x : xs) (_ : _ : ys) =
      let (first, second) = go xs ys
      in (x : first, second)
    go xs _ = ([], xs)

Haskell 中的 let 模式绑定默认是惰性的。这样，go 可以先返回外层元组和第一半的一个 cons。只有需要后续元素时，才会继续求值递归结果。

原实现为什么会强制递归

原代码中的这一步：

mapFst (x :) $ go xs ys

等价于把 go xs ys 传给：

mapFst f (x, y) = (f x, y)

为了匹配 (x, y)，mapFst 必须先检查参数是不是元组，也就是把 go xs ys 求值到元组构造器。这个检查会沿递归链继续进行，直到 go xs ys 到达基例并返回元组。因此，测试中的 tailEnd 0 会触发 error "read too deep"。增加缓冲深度只会把错误推迟，并不会改变求值方式。

为什么改写后可以按需读取

新版本直接构造：

(x : first, second)

构造外层元组时，不需要先求值 first 或 second。first 和 second 来自惰性的 let 模式绑定，所以函数可以先返回第一半当前的 cons，而不必先求完整个递归结果。需要更多第一半元素时，函数才会按原有的快慢指针递归检查输入。

例如，取第一半的前几个元素：

take n (fst (halve input))

函数只会继续求出满足这些元素所需的递归部分。具体要检查多少输入，取决于请求的深度，以及输入是否满足 go 的模式匹配。并非所有输入都能避开末尾检查：要确认某个位置之后没有更多第一半元素，仍可能需要检查输入的后续结构。

测试中的报错含义

测试构造的输入是 x ++ x ++ tailEnd bufferDepth。它要验证的是：读取第一半中对应于 x 的元素时，不会继续触及缓冲区末尾。原实现为了生成第一个结果元组，会沿递归链检查列表，因此读到 tailEnd 0 并抛出异常。改写后，读取第一半的前缀时，不会再因为 mapFst 强制求值递归结果而提前走到基例。