[Haskell-cafe] efficient chop

[wren ng thornton]

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