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)

Answer 2

在使用严格评估解决您的问题时，我建议您重用标准函数来计算间隔长度：

countNames :: String -> String -> Int
countNames start end = (+) 1 . length . takeWhile (/= end) $ iterate nextName start

解释：

• iterate生成一个无限列表nextName：[start, nextname start, nextname (nextName start), ...]
• takeWhile (/= end)保留列表元素，直到达到预期值（不包括上限）；
• 然后你取length并加 1。