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
