[Haskell-cafe] efficient chop

Roman Cheplyaka roma at ro-che.info
Wed Sep 14 09:11:46 CEST 2011


* Kazu Yamamoto <kazu at iij.ad.jp> [2011-09-14 15:59:05+0900]
> Hello,
> 
> My friend reached the following version:
> 
> chop :: String -> String
> chop = foldr go []
>   where
>     go x xs
>       | isSpace x && null xs = []
>       | otherwise            = x:xs
> 
> This version is faster than the reverse version in most cases.  The
> point is checking "isSpace" first and falling into "otherwise" in many
> cases, which is a natural co-recursion.

This was exactly my first attempt on rewriting your foldr version.

Unfortunately, it doesn't seem faster at all (foldr2 below).
The test input was replicate 100 'a' ++ replicate 100 ' '.
GHC 7, -O2.

benchmarking all/foldr
mean: 2.808462 us, lb 2.807047 us, ub 2.810520 us, ci 0.950
std dev: 8.620822 ns, lb 6.535738 ns, ub 11.59552 ns, ci 0.950

benchmarking all/reverse
mean: 4.128217 us, lb 4.125409 us, ub 4.134086 us, ci 0.950
std dev: 20.07591 ns, lb 11.47572 ns, ub 38.33738 ns, ci 0.950

benchmarking all/foldr2
mean: 6.701714 us, lb 6.692093 us, ub 6.711627 us, ci 0.950
std dev: 50.06638 ns, lb 42.25004 ns, ub 64.84223 ns, ci 0.950


-- 
Roman I. Cheplyaka :: http://ro-che.info/



More information about the Haskell-Cafe mailing list