CODEWITHSUNDEEP
haskell
santosh
santosh

Reputation: 315

space leak in simple string generation. why?

-- 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?

Upvotes: 3

Views: 179

Answers (2)

Nicolas
Nicolas

Reputation: 24769

While using strict evaluation fix your issue, I would recommend you to reuse standard function to compute the interval length:

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

Explanation:

  • iterate generate an infinite list of nextName: [start, nextname start, nextname (nextName start), ...];
  • takeWhile (/= end) keep the list elements until you reach the expected value (excluding the upper bound);
  • then you take the length and add 1.

Upvotes: 5

Satvik
Satvik

Reputation: 11218

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)

Upvotes: 8

Related Questions