inits

[Chris Kuklewicz]

Nils Anders Danielsson wrote:
> On Mon, 10 Apr 2006, Chris Kuklewicz <haskell at list.mightyreason.com> wrote:
> 
>> If the goal is speed, then this definition is running over 10% faster with ghc
>> -O2 on my powerbook for (sum $ map length $ inits [1..10000])
>>
>> inits' = helper id
>>     where helper f [] = (f []):[]
>>           helper f (x:xs) = (f []):helper (f.(x:)) xs
> 
> This function looks like it's exactly equivalent to the H98 one, but I
> haven't checked the details.

The Haskell 98 Report http://www.haskell.org/onlinereport/list.html gives:

> -- inits xs returns the list of initial segments of xs, shortest first.
> -- e.g., inits "abc" == ["","a","ab","abc"]
> inits                   :: [a] -> [[a]]
> inits []                =  [[]]
> inits (x:xs)            =  [[]] ++ map (x:) (inits xs)

Which, using ghc-6.4.2 -O2, runs the benchmark operation that I am using (sum $
map length $ inits [1..10000]) in 50.9 seconds.  (Just as fast as GHC's
Data.List.init, so I expect that GHC uses the code in the report).

The actual timing output:

> pamac-cek10:/tmp chrisk$ time ./i6
> 50005000
> 
> real    0m56.197s
> user    0m49.856s
> sys     0m1.003s

The helper code runs in 5.2 seconds:

> pamac-cek10:/tmp chrisk$ time ./i2
> 50005000
> 
> real    0m5.750s
> user    0m5.114s
> sys     0m0.111s

Running with +RTS -sstderr -RTS shows the code in the report is allocating
exactly 4 times as much space on the heaps.  The speed does not change if I use

main = print $ sum $ map length $ inits2 (take 10000 [True,True ..])

> Furthermore, this definition made me think of a flaw in many of the
> others: they won't work for infinite lists. (Note that
> length ([1..] :: [Int]) = maxBound :: Int.)
> 

Subtle problem.  But [1..] defaults to Integer which is "infinite" enough.  The
original example will need to use genericTake . . .