我有以下函数，它计算两个字符串之间的差异数：
distance1 :: String -> String -> Int
distance1 list1 list2 = length . filter (uncurry (/=)) $ zip list1 list2
它工作得很好。可以在恒定空间内处理任何大小的列表。
我也在玩 - 比方说 - 这个函数的低级、基于递归、不好的实现，并具有以下内容：
distance2 :: String -> String -> Int
distance2 list1 list2 = distanceHelper 0 0
where
distanceHelper index result
| index == length list1 = result
| otherwise = distanceHelper (index + 1) (result + diff)
where
char1 = list1 !! index
char2 = list2 !! index
diff = if char1 /= char2 then 1 else 0
我知道按索引访问链表很糟糕，但在这里我不是担心时间，而是担心空间。由于它是尾递归的，我希望它也可以在恒定空间内为任何大小的列表运行。
以下是用于测试的程序：
main :: IO ()
main = print $ distance2 list1 list2
where
list1 = replicate count 'A'
list2 = replicate count 'B'
count = 100000000
如果我要distance1以任何大小（例如 100000000000000000）运行一个，是的，它会运行很长时间，但它会消耗大约 3-4 MB 并且无论如何都会完成这项工作。
如果我将使用distance2（仅使用 100000000）运行测试，它会立即消耗大量内存（约 1G），但随后将停止消耗内存并继续完成工作而不会消耗更多内存。所以它给人的印象是它也为恒定空间运行，但那个空间太多了。
我想了解为什么第二个版本需要这么多内存？
注意：以防万一尝试使用 bang 模式的第二个版本distanceHelper !index !result，即将内部函数声明为，但这没有帮助。
我知道按索引访问链表很糟糕，但在这里我不是担心时间，而是担心空间。由于它是尾递归的，我希望它也可以在恒定空间内为任何大小的列表运行。
不，这正是这里的问题。
如果使用 生成列表replicate count 'A'，则可以延迟生成。如果我们访问第一个元素，丢弃它，然后是第二个，丢弃它，依此类推，计算可以在常量空间中执行，因为元素在被丢弃后可以被快速垃圾回收。这要求消费者是这样的
consume [] = ...
consume (x:xs) = .... (consume xs) -- x was used and then discarded
如果我们改为使用!!访问列表，编译器就不能再丢弃列表元素。毕竟，我们可以稍后!!使用我们很久以前使用的元素进行请求。因此，count元素的完整列表必须存储在内存中。
现在，一个非常聪明的编译器可能会执行静态分析并证明 中使用的索引!!是严格递增的，我们确实可以丢弃/垃圾收集列表的前缀。不过，大多数编译器并不那么聪明。
此外， length这里也使用：
distanceHelper index result
| index == length list1 = result
...
length list1如果它可以消耗list1，则将在恒定空间中工作，即如果list1之后不再使用。情况并非如此，因此这将强制使用count单元格生成完整列表并将其保存在内存中。我们应该避免length和的另一个原因!!。
强调上面的一点：
let list = replicate count 'A'
in length list
应该是恒定空间，而
let list = replicate count 'A'
in length list + length list
不能（除非非常聪明的优化），因为我们不能list在第一次length调用时使用它——我们稍后在第二次调用时需要它。
更微妙的是，
let list () = replicate count 'A'
in length (list ()) + length (list ())
将在常量空间中工作，因为函数调用的结果没有被缓存。上面，我们生成（并使用）列表两次，这可以在常量空间中完成。