haskell - 简单字符串生成中的空间泄漏。为什么？

Question

-- generates names in the following order
-- a, b, c ... z, aa, ba, ca, ... za, ab, bb, cb ...
nextName :: String -> String
nextName [] = "a"
nextName (x:xs) = if x == 'z' then 'a' : nextName xs else succ x : xs

-- verify if the number of names generated is as expected.
countNames :: String -> String -> Int
countNames start end = loop 1 start
    where
        loop acc next =
            if next == end then
                acc
            else
                loop (acc + 1) (nextName next)

运行 countNames "a" "zzzzzz"在 ghci

在我的 com 上运行它占用了整个内存并需要大量时间才能完成。

如果有人指出发生空间泄漏的位置和原因，不胜感激？

Answer 1

问题是一个大的计数器重击，因为循环对计数器不严格acc .通常的解决方案是使用 seq或 BangPatterns使其严格。这是使用 BangPatterns 的解决方案.

{-# LANGUAGE BangPatterns #-}
-- generates names in the following order
-- a, b, c ... z, aa, ba, ca, ... za, ab, bb, cb ...
nextName :: String -> String
nextName [] = "a"
nextName (x:xs) = if x == 'z' then 'a' : nextName xs else succ x : xs

-- verify if the number of names generated is as expected.

countNames :: String -> String -> Int
countNames start end = loop 1 start
    where
        loop !acc next =
            if next == end then
                acc
            else
                loop (acc + 1) (nextName next)