inits
Chris Kuklewicz
haskell at list.mightyreason.com
Mon Apr 10 16:43:25 EDT 2006
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 . . .
More information about the Libraries
mailing list