[SOLVED] Haskell words implementation

Haskell words implementation

I tried to implement words function from Data.List, but my implementation doesn't work exactly as I wish.

For example, if the function's input is "tere vana kere" then the output is ["vana", "kere"] and it misses the first word. But when I add space in front of my input " tere vana kere" then the output is correct ["tere", "vana", "kere"]

Could someone point out the problem. Thank You

words' :: String -> [String]
words' xs = snd $ foldr (\x acc -> if isSpace x then 
                                    if null (fst acc) then
                                        acc
                                    else
                                        ([], (fst acc): (snd acc)) 
                               else 
                                     (x:fst acc, snd acc)   
                               ) ([],[]) xs

Solution

OK, so let's try this:

step x acc =
  if isSpace x
    then
      if null (fst acc)
        then acc
        else ([], (fst acc) : (snd acc))
    else (x : fst acc, snd acc)

words' xs = snd $ foldr step ([], []) xs

Now let's walk this through, one step at a time: Suppose we want words' "ABC DEF GHI". We can do it like this:

Prelude> step 'I' ([], [])
("I", [])
Prelude> step 'H' it
("HI", [])
Prelude> step 'G' it
("GHI", [])
Prelude> step ' ' it
("", ["GHI"])
Prelude> step 'F' it
("F", ["GHI"])
Prelude> step 'E' it
("EF", ["GHI"])
Prelude> step 'D' it
("DEF", ["GHI"])
Prelude> step ' ' it
("", ["DEF","GHI"])
Prelude> step 'C' it
("C", ["DEF","GHI"])
Prelude> step 'B' it
("BC", ["DEF","GHI"])
Prelude> step 'A' it
("ABC", ["DEF","GHI"])
Prelude> snd it
["DEF","GHI"]

Do you see the problem here?

The trouble is, you only "flush" the current word into the word list when you see a space character. In particular, you don't flush when you see the end of the input. You can fix that by replacing snd:

words' xs = (\ (w, ws) -> w:ws) $ foldr step ([], []) xs

As an aside, congrats on making the code correctly handle multiple consecutive spaces. :-)

EDIT: To preserve that nice property:

words' xs = (\ (w, ws) -> if null w then ws else w:ws) $ ...