Performance/Laziness
| Haskell Performance Resource
Constructs: Techniques: |
The Zen of Laziness: Making it do the hard work
To look at how laziness works in Haskell, and how to make it do efficient work, we'll implement a merge sort function. It will have the type:
merge_sort :: (Ord a) => [a] -> [a]
We'll also need a function to split the list in two, I'll call this cleaving, and it will look like this:
cleave :: [a] -> ([a],[a])
Let's start by implementing the cleaving function. The conventional way to split a list in merge sort is to take the first N/2 elements off the front, and the remaining elements after this number. The problem is that finding the length of a list in haskell is expensive. So instead, we'll take pairs of elements off the front. Define two functions:
evens [] = [] evens [x] = [x] evens (x:_:xs) = x : evens []
odds [] = [] odds [x] = [] odds (_:x:xs) = x : odds []
and use them to implement cleave:
cleave xs = (evens xs, odds xs)
Experience in a strictly evaluation langauge like SML or Objective CAML may lead you to write alternate versions using an accumulating parameter. Assuming that reversing the order of the elements doesn't matter, you could use this function to split the list into even and odd elements and implement the cleave function as follows:
cleave = cleave' ([],[]) where
cleave' (eacc,oacc) [] = (eacc,oacc)
cleave' (eacc,oacc) [x] = (x:eacc,oacc)
cleave' (eacc,oacc) (x:x':xs) = cleave' (x:eacc,x':oacc) xs