[Haskell-cafe] efficient chop
wren ng thornton
wren at freegeek.org
Wed Sep 14 20:20:16 CEST 2011
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 
-- 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 .
More information about the Haskell-Cafe