<div dir="ltr"><div><div><div>Summary: yes, we can, by a LOT. Yes, I know how. Yes, I've done some benchmarking to demonstrate. Yes, it is even very simple. And yes, the results are correct, including laziness requirements.<br>
</div><div><br>Background: I was looking at the code for Data.List.inits in base-4.7.0.0 (function renamed for clarity):<br><br>initsDL                   :: [a] -> [[a]]<br>initsDL xs                =  [] : case xs of<br>
                                  []      -> []<br>                                  x : xs' -> map (x :) (initsDL xs')<br><br>The recursive maps made me suspicious. I decided to try writing a different version:<br>
<br>initsHO xs = map ($ []) (scanl q id xs)<br>  where<br>    q f x = f . (x:)<br><br></div>I mentioned this on #haskell and noted that it would be a nice exercise to write it with less fancy function footwork using map reverse. rasfar responded (modulo naming) with<br>
<br>initsR xs = map reverse (scanl q [] xs)<br>  where<br>    q acc x = x : acc<br><br></div>rasfar ran a few informal benchmarks suggesting that initsR is faster than initsHO, which in turn is significantly faster than the current implementation in Data.List. I have now run Criterion benchmarks testing performance in three ways: reduction of inits [1..n] to normal form, reduction of (inits [1..n])!!(n-1) to normal form, and reduction of (length (inits [1..n])) to normal form. In each case the Criterion test case is the list [1..n], so there is no risk of some sort of weird fusion occurring. The results are extremely clear in all three test scenarios, with a variety of values of n:  initsR is a little faster than initsHO, and inits HO is much, much faster than initsDL. The differences become apparent even for small values of n (10-50), but when n gets up to 100000, you don't even want to wait for initsDL to finish. This was all using ghc 7.8.3 with -O2. I've attached my benchmarking code, which also includes some basic correctness and laziness tests. Note that the first group of benchmarks tests a variety of vaues of n. For the second group, I was tired so I just twiddled it by hand. For the third group... Criterion estimated that benchmarking length(initsDL(100000)) would take 124582.9 seconds, so I decided to stop there.<br>
<br></div>Conclusion: we should replace Data.List.inits with initsR, unless someone comes up with something that beats initsR.<br></div>