很难理解 Haskell 内存分配行为

Question

我偶然发现了 Haskell 和 FP，并对其中的可能性感到震惊。我内心的老数学书呆子可以毫不费力地为实际有用的目的编写简单的代码。然而，尽管进行了所有阅读，我仍然很难理解如何不遇到一些令人惊讶的性能瓶颈。

因此，我使用简单的实现编写了非常短的代码，然后尝试进行一些小的更改以查看性能如何响应。 这是一个我真的无法理解的例子...我编写了这个函数，它找到了 约瑟夫斯问题，故意使用简单的列表实现。

m = 3
n = 3000
main = putStr $ "Soldier #" ++ (show $ whosLeft [1..n]) ++ " survived...\n"

whosLeft [lucky] = lucky
whosLeft soldiers = whosLeft $ take (length soldiers -1) $ drop m $ cycle soldiers

根据 RTS，后者的运行时间为 190 毫秒，生产率为 63%。

然后我想尝试的第一件事是删除（长度士兵-1）并将其替换为递减整数。

运行时间跃升至 900 毫秒，生产率下降至 16%，并且使用的内存比上面更简单的代码多 47 倍！所以我添加了严格的评估，强制使用 Int 类型，尝试了删除全局变量等，但没有多大效果。我就是无法理解这种放缓。

m = 3::Int
n = 3000::Int
main = putStr $ "Soldier #" ++ (show $ whosLeft n [1..n]) ++ " survived...\n"

whosLeft 1 [lucky] = lucky
whosLeft n' soldiers = n' `seq` left `seq` whosLeft (n'-1) left
                where left = take (n'-1) $ drop m $ cycle soldiers

我已经筛选了与性能相关的文章和帖子，但我似乎没有得到任何关于这一点的提示。作为一个 Haskell 菜鸟，我一定错过了一些大东西...这个添加的参数（预先咀嚼的计算...）怎么会降低速度这么多？

PS：我知道，如果约瑟夫斯真的和三千士兵在一起，他们就不需要自杀了……

Answer 1

第一个解决方案通过获取士兵列表的长度来强制其整个脊柱。第二种解决方案仅强制（使用seq）士兵列表的head。将 seq 之间的 left 替换为 length left，您将恢复性能。