performance - Haskell:在大列表中找到最大值时堆栈溢出

Question

我有以下 problem 1-4 of the Matasano Cryptopals Challenge 的实现，用于在文件中找到一行，该行是与单个字节异或的文本字符串。它适用于大文件，但显示“堆栈空间溢出:当前大小 8388608 字节”。对于提供的文件。

import System.IO
import System.Environment
import Control.Monad
import Data.Bits
import Data.Word
import Data.Maybe
import Data.List hiding (maximumBy)
import Data.Char
import Data.Ord
import Data.Foldable hiding (sum)


hexChars = "0123456789ABCDEF"

hexToBytes :: String -> Maybe [Word8]
{- Converts a hex string into a byte array -}

hexToBytes hexes = hexToBytes' (map toUpper hexes)
hexToBytes' (char1 : char2 : xs) = do
    tail <- hexToBytes' xs
    byte1 <- char1 `elemIndex` hexChars
    byte2 <- char2 `elemIndex` hexChars
    return ((fromIntegral(byte1*16 + byte2) :: Word8) : tail)
hexToBytes' [_] = Nothing
hexToBytes' [] = Just []

maxBy :: Ord b => Foldable f => (a -> b) -> f a -> a
maxBy = maximumBy . comparing

bytesToString :: Integral i => Monad m => m i -> m Char
bytesToString = liftM (chr . fromIntegral)  

isLowercase x = (x >= 'a') && (x <= 'z')

asciiCheck :: Word8 -> Int
asciiCheck x = if (isLowercase . chr . fromIntegral) x then 1 else 0

score = (sum . map asciiCheck)

readLines :: Handle -> IO [String]
readLines handle = do
    eof <- hIsEOF handle
    if eof then
        return []
    else liftM2 (:) (hGetLine handle) (readLines handle)

decode key = map (xor key)

keys = [minBound ..] :: [Word8]

massDecode inputs =
    maxBy score (liftM2 decode keys inputs)

main = do
    hSetEncoding stdout latin1
    args <- getArgs
    handle <- case args of
        [] -> return stdin
        (x:xs) -> openFile x ReadMode
    lines <- readLines handle
    putStrLn $ bytesToString $ massDecode $ catMaybes $ map hexToBytes lines

该程序通过遍历一个列表来工作，该列表包含每个输入行与每个可能的键异或。我怀疑这个大列表以某种方式导致溢出，但我认为这不会导致内存问题，因为该列表会延迟生成。我不认为我对何时评估 thunk 有足够坚定的理解，无法凭直觉判断这是如何导致堆栈溢出的。

所以我的问题是:为什么生成或遍历此列表会导致堆栈溢出？

Answer 1

如 this thread 中所述，我们现在在前奏中的列表中的 maximumBy 并不是最佳性能，出于各种原因，我们只说“原因”。

如果您使用建议的 maximumBy' 函数，它是严格的，您可能会修复泄漏:

foldl1' f l = foldl' f (head l) (tail l)

maximumBy' f = foldl1' max'
  where max' x y = case f x y of
                        GT -> y
                        _  -> x