Lazy Evaluation and Time Complexity
I was looking around stackoverflow Non-Trivial Lazy Evaluation, which led me to Keegan McAllister's presentation: Why learn Haskell. In slide 8, he shows the minimum function, defined as:
minimum = head . sort
and states that its complexity is O(n). I don't understand why the complexity is said to be linear if sorting by replacement is O(nlog n). The sorting referred in the post can't be linear, as it does not assume anything about the data, as it would be required by linear sorting methods, such as counting sort.
Is lazy evaluation playing a mysterious role in here? If so, what is the explanation behind it?
In minimum = head . sort, the sort won't be done fully, because it won't be done upfront. The sort will only be done as much as needed to produce the very first element, demanded by head.
In e.g. mergesort, at first n numbers of the list will be compared pairwise, then the winners will be paired up and compared (n/2 numbers), then the new winners (n/4), etc. In all, O(n) comparisons to produce the minimal element.
mergesortBy less [] = []
mergesortBy less xs = head $ until (null.tail) pairs [[x] | x <- xs]
where
pairs (x:y:t) = merge x y : pairs t
pairs xs = xs
merge (x:xs) (y:ys) | less y x = y : merge (x:xs) ys
| otherwise = x : merge xs (y:ys)
merge xs [] = xs
merge [] ys = ys
The above code can be augmented to tag each number it produces with a number of comparisons that went into its production:
mgsort xs = go $ map ((,) 0) xs where
go [] = []
go xs = head $ until (null.tail) pairs [[x] | x <- xs] where
....
merge ((a,b):xs) ((c,d):ys)
| (d < b) = (a+c+1,d) : merge ((a+1,b):xs) ys -- cumulative
| otherwise = (a+c+1,b) : merge xs ((c+1,d):ys) -- cost
....
g n = concat [[a,b] | (a,b) <- zip [1,3..n] [n,n-2..1]] -- a little scrambler
Running it for several list lengths we see that it is indeed ~ n:
*Main> map (fst . head . mgsort . g) [10, 20, 40, 80, 160, 1600]
[9,19,39,79,159,1599]
To see whether the sorting code itself is ~ n log n, we change it so that each produced number carries along just its own cost, and the total cost is then found by summation over the whole sorted list:
merge ((a,b):xs) ((c,d):ys)
| (d < b) = (c+1,d) : merge ((a+1,b):xs) ys -- individual
| otherwise = (a+1,b) : merge xs ((c+1,d):ys) -- cost
Here are the results for lists of various lengths,
*Main> let xs = map (sum . map fst . mgsort . g) [20, 40, 80, 160, 320, 640]
[138,342,810,1866,4218,9402]
*Main> map (logBase 2) $ zipWith (/) (tail xs) xs
[1.309328,1.2439256,1.2039552,1.1766101,1.1564085]
The above shows empirical orders of growth for increasing lengths of list, n, which are rapidly diminishing as is typically exhibited by ~ n log n computations. See also this blog post. Here's a quick correlation check:
*Main> let xs = [n*log n | n<- [20, 40, 80, 160, 320, 640]] in
map (logBase 2) $ zipWith (/) (tail xs) xs
[1.3002739,1.2484156,1.211859,1.1846942,1.1637106]
edit: Lazy evaluation can metaphorically be seen as kind of producer/consumer idiom1, with independent memoizing storage as an intermediary. Any productive definition we write, defines a producer which will produce its output, bit by bit, as and when demanded by its consumer(s) - but not sooner. Whatever is produced is memoized, so that if another consumer consumes same output at different pace, it accesses same storage, filled previously.
When no more consumers remain that refer to a piece of storage, it gets garbage collected. Sometimes with optimizations compiler is able to do away with the intermediate storage completely, cutting the middle man out.
1 see also: Simple Generators v. Lazy Evaluation by Oleg Kiselyov, Simon Peyton-Jones and Amr Sabry.
Suppose minimum' :: (Ord a) => [a] -> (a, [a]) is a function that returns the smallest element in a list along with the list with that element removed. Clearly this can be done in O(n) time. If you then define sort as
sort :: (Ord a) => [a] -> [a]
sort xs = xmin:(sort xs')
where
(xmin, xs') = minimum' xs
then lazy evaluation means that in (head . sort) xs only the first element is ever computed. This element is, as you see, simply (the first element of) the pair minimum' xs, which is computed in O(n) time.
Of course, as delnan points out, the complexity depends on the implementation of sort.
You've gotten a good number of answers that tackle the specifics of head . sort. I'll just add a couple more general statments.
With eager evaluation, the computational complexities of various algorithms compose in a simple manner. For example, the least upper bound (LUB) for f . g must be the sum of the LUBs for f and g. Thus you can treat f and g as black boxes and reason exclusively in terms of their LUBs.
With lazy evaluation, however, f . g can have a LUB better than the sum of f and g's LUBs. You can't use black-box reasoning to prove the LUB; you must analyze the implementations and their interaction.
Thus the often-cited fact that complexity of lazy evaluation is much harder to reason about than for eager evaluation. Just think about the following. Suppose you're trying to improve the asymptotic performance of a piece of code whose form is f . g. In an eager language, there's on obvious strategy you can follow to do this: pick the more complex of f and g, and improve that one first. If you succeed at that, you succeed at the f . g task.
In a lazy language, on the other hand, you can have these situations:
- You improve the more complex of
fandg, butf . gdoesn't improve (or even gets worse). - You can improve
f . gin ways that don't help (or even worsen)forg.
The explanation depends on the implementation of sort, and for some implementations it will not be true. For instance with an insert sort that inserts at the end of the list, lazy evaluation does not help. So lets choose an implementation to look at, and for the sake of simplicity, lets use selection sort:
sort [] = []
sort (x:xs) = m : sort (delete m (x:xs))
where m = foldl (\x y -> if x < y then x else y) x xs
The function clearly uses O(n^2) time to sort the list, but since head only needs the first element of the list, sort (delete x xs) is never evaluated!