简单字符串生成中的空间泄漏.为什么

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)

在GHCI运行countNames "a" "zzzzzz"

在我的 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。