space leak in simple string generation. why?

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)

run countNames "a" "zzzzzz" in ghci

running it on my com takes up the whole of the memory and takes a hell of lot of time to complete.

appreciate it if anyone indicate where and why space leak is happening?

Answer 1

The problem is a large counter thunk because loop is not strict on the counter acc. The usual solution is to use seq or BangPatterns to make it strict. Here is the solution using 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)