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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
