Implementing Haskell#lines

Question

Learn You a Haskell shows the lines function:

It takes a string and returns every line of that string in a separate list.

Example:

>lines' "HELLO\nWORLD\nHOWAREYOU"
["HELLO","WORLD","HOWAREYOU"]

Here's my implementation:

lines' :: String -> [String]
lines' [] = []
lines' xs = lines'' xs []
             where lines'' [] ys = ys : []
                   lines'' (x:xs) ys 
                     |  x == '\n' = ys : lines'' xs []
                     | otherwise  = lines'' xs (ys ++ [x])

Please critique it. Also, when using an accumulator value (such as ys in lines''), I don't know how to use the : function instead of ++.

Answer 1

1. What happens when a string ends in a newline? lines "\n" ⇒ [""], but lines' "\n" ⇒ ["", ""].

2. ys could have a more informative name. line?

3. When you find yourself wanting to add new items to the end of a list, consider keeping the list in reverse order, adding items to the front and reversing it when it's done. This avoids needing to use ++. ("Done" is a fuzzy concept when working lazily with infinite lists.)

4. ...but when reinventing the wheel, you needn't reinvent the axle and bearings as well. There is a Prelude function that will parse one line from a string: break. If you use that, you need only handle recursing on the remainder. This is how lines is really implemented.

   lines s         =  let (l, s') = break (== '\n') s
                      in  l : case s' of
                                   []      -> []
                                   (_:s'') -> lines s''