我已经开始深入研究Haskell，试图解决一些小问题。
我偶然发现了">标准哈斯克尔友好">解决方案和我的"非常丑陋和哈斯克尔不友好">版本之间的巨大性能差异(~100-200x(。
我敢肯定，对于哈斯克勒同胞来说，这种表现的差异是有充分理由的，我错过了，并且可以在这个话题上教育我。
问题：在数字字符串中查找最大 5 位数字
两者都在求解中使用相同的概念：生成所有 5 位数字并找到最大值。
优雅快速的代码
digit5 :: String -> Int
digit5 = maximum . map (read . take 5) . init . tails
丑陋且非常慢的代码(一旦字符串大小很大(
digit5' :: String -> String -> String
-- xs - input string
-- maxim - current maximal value
digit5' xs maxim
| (length xs) < 5 = maxim
| y > maxim = digit5' (drop 1 xs) y -- use new detected maximum value
| otherwise = digit5' (drop 1 xs) maxim
where y = take 5 xs
digit5 :: String -> Int
digit5 xs
-- return the original string if the input size is smaller than 6
| length (xs) < 6 = read xs
| otherwise = read $ digit5' xs "00000"
对于小输入，我得到大致相同的执行时间，对于大输入，我开始看到非常大的差异(对于 44550 个元素的输入(：
Computation time for ugly version: 2.047 sec
Computation time for nice version: 0.062 sec
我对此的肤浅理解是，快速代码使用的是预先可用的高阶函数。对于较慢的版本，使用递归，但我认为咬尾巴应该是可能的。但在天真的层面上，在我看来，两者似乎都在做同样的事情。
虽然较慢的函数对字符串进行比较而不是将它们转换为数字，但我也尝试将字符串转换为整数，但没有任何大的改进
我尝试使用没有任何标志和以下命令的 ghc 进行编译：
ghc
ghc -O2
ghc -O2 -fexcess-precision -optc-O3 -optc-ffast-math -no-
recomp
stack runhaskell
ghc -O3
为了可重现性，我添加了一个指向代码的链接，也连接了测试向量：https://pastebin.com/kuS5iKgd
您的"慢速"版本的问题在于这一行：
| length xs < 5 = maxim
这计算了xs的长度，并且因为Haskell列表是单向链表，所以此操作需要完全遍历整个列表，即O(n(。它发生在每次迭代中。并且有 N 次迭代。这使得整个过程为 O(n^2(。
另一方面，"快速"代码只是线性的，在大输入上表现得淋漓尽致。
如果您只是将有问题的行替换为以下内容：
| null xs = maxim
它将使整个事情变得线性，并且与"优雅"解决方案一样快。当然，这将导致额外的 5 次迭代，但通过降低整体复杂性可以弥补这种损失。
或者，您也可以通过过滤掉 5 个字符或更短的尾巴来使"优雅"解决方案同样慢：
digit5 = maximum . map (read . take 5) . filter ((>= 5) . length) . tails