Jaro Reinders jaro.reinders at gmail.com
Thu Aug 1 07:58:15 UTC 2019

```I think the best way to test the performance is to use a benchmarking
library such as criterion (http://www.serpentine.com/criterion/)

import Criterion.Main
import Data.List (inits,tails)

splits1, splits2, splits3 :: [a] -> [([a],[a])]
splits1 xs = zip (inits xs) (tails xs)

splits2 [] = [([],[])]
splits2 xs@(x:xs') = ([],xs) : [(x:as,bs) | (as,bs) <- splits2 xs']

splits3 = go id where
go prefix xs = (prefix [],xs) : case xs of
x:xs -> go (prefix . (x :)) xs
[] -> []

main = defaultMain
[ bench "splits1" \$ nf splits1 input
, bench "splits2" \$ nf splits2 input
, bench "splits3" \$ nf splits3 input
]
where
input :: [Int]
input = [1..1000]

It gives the following results on my computer:

benchmarking splits1
time                 4.693 ms   (4.625 ms .. 4.752 ms)
0.999 R²   (0.998 R² .. 0.999 R²)
mean                 4.725 ms   (4.694 ms .. 4.758 ms)
std dev              97.37 μs   (77.95 μs .. 123.3 μs)

benchmarking splits2
time                 12.10 ms   (11.96 ms .. 12.25 ms)
0.999 R²   (0.999 R² .. 1.000 R²)
mean                 12.08 ms   (12.03 ms .. 12.14 ms)
std dev              149.7 μs   (110.0 μs .. 199.1 μs)

benchmarking splits3
time                 4.110 ms   (4.025 ms .. 4.187 ms)
0.997 R²   (0.996 R² .. 0.999 R²)
mean                 4.124 ms   (4.081 ms .. 4.177 ms)
std dev              147.6 μs   (115.6 μs .. 238.5 μs)
variance introduced by outliers: 17% (moderately inflated)

On 01-08-2019 04:45, Todd Wilson wrote:
> Dear Cafe:
>
> I'm getting to the point in my Haskell learning curve where I'm
> getting more interested in the fine points of programming for
> performance and would be grateful for some ideas of the tools and
> options available for exploring this. To make this concrete, let me
> give a simple example. Here are two different ways of coding the same
> list-splitting function:
>
>    import Data.List (inits,tails)
>    splits1, splits2 :: [a] -> [([a],[a])]
>    splits1 xs = zip (inits xs) (tails xs)
>    splits2 [] = [([],[])]
>    splits2 xs@(x:xs') = ([],xs) : [(x:as,bs) | (as,bs) <- splits2 xs']
>
> For example, splits1 [1,2,3] is
> [([],[1,2,3]),([1],[2,3]),([1,2],[3]),([1,2,3],[])].
>
> How do these functions compare in their actual time and space usage?
> It seems that, asymptotically, tails is O(n) while inits is O(n^2) in
> both time and space (when fully evaluated), and splits2 is also
> O(n^2), but how would I go about comparing them in actual usage to get
> a more precise comparison? What profiling or run-time statistics could
> I gather to make a decision about which one to use in a situation
> where performance mattered (assuming for the sake of discussion that
> such a situation existed for this simple example)? And, out of
> curiosity, is there an even more efficient way to code this function?
> Thanks,
>
> Todd Wilson
> _______________________________________________