On 9/13/11 11:03 PM, Kazu Yamamoto (山本和彦) wrote:
Hello Cafe,
I would like to have an efficient implementation of the chop function. As you guess, the chop function drops spaces in the tail of a list.
chop " foo bar baz " -> " foo bar baz"
A naive implementation is as follows:
chopReverse :: String -> String chopReverse = reverse . dropWhile isSpace . reverse
But this is not elegant.
Just consider it as an automaton/transducer problem, namely a PDA: chop = go 0 [] where -- go :: State -> Stack -> String -> String go 0 _ [] = [] go 0 _ (x:xs) | isSpace x = go 1 [x] xs | otherwise = x : go 0 xs go 1 ss [] = [] go 1 ss (x:xs) | isSpace c = go 1 (x:ss) xs | otherwise = reverse ss ++ x : go 0 xs Of course you can optimize this implementation. You don't actually need the state argument, since it's encoded by the emptiness/non-emptiness of the remembered spaces. And if you only care about (==' ') instead of isSpace, then you don't need to reverse the spaces when adding them back on. Also, if you only care about (==' '), you could just keep track of the number of spaces instead of the actual list of them; or if you do care about isSpace you could also use a difference list instead of doing the reversal--- though I'm not sure which is more optimal here. As a transducer, this version can produce the output with minimal delays; whereas your foldr implementation needs to traverse the whole string before it can return the first character. If you want proper list-fusion (instead of just laziness), you could also use the `build` function to abstract over (:) and []. -- Live well, ~wren