6
\$\begingroup\$

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?

\$\endgroup\$
6
\$\begingroup\$

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)
\$\endgroup\$
4
\$\begingroup\$

Another way to do it:

aStar = iterate ('a':) ""
\$\endgroup\$
  • 3
    \$\begingroup\$ You should explain why this is a better way to do this instead of just providing an alternate solution. \$\endgroup\$ – Hosch250 Aug 30 '15 at 4:34
  • 6
    \$\begingroup\$ @Hosch250 Normally, I'd agree that code dump answers aren't acceptable. However, this solution is so obviously simpler and better in every way. \$\endgroup\$ – 200_success Aug 30 '15 at 4:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.