Infinite list of strings containing 'a'

Question

I was assigned to write a piece of Haskell code that makes an infinite list containing increasing numbers of 'a's.

My first thought was to write it as a list comprehension like this:

aStar = [replicate n 'a' | n <- [0..]]

But when I asked my professor he said I should use explicit recursion so I came up with this:

aStar :: [String]
--repeats a string from 0
aStar = repeat' 0 'a'

repeat' :: Int -> Char -> [String]
repeat' n x = [cycle' x n] ++ repeat' (n + 1) x
    where cycle' _ 0 = ""
          cycle' y z = [y] ++ cycle' y (z - 1) 

Is there a shorter way to do it?

Answer 1

Both of your solutions have efficiency issues, but at least your original list comprehension has the advantage of being short and readable. Your revised solution is arguably worse.

The problem with replicate is that each string is rebuilt from scratch.

The problem with the second solution is that you are using ++, which appends to the end of a list. That requires traversing to the end of the list, which gets more and more time-consuming as the lists get longer. Anytime you write ++, you should try hard to find a better approach.

This is the solution that your professor probably had in mind (note the use of : rather than ++):

aStar :: [String]
aStar = aStar' 'a' ""
  where
    aStar' c s = s : aStar' c (c : s)

Answer 2

Another way to do it:

aStar = iterate ('a':) ""