Personal tools

Performance/Laziness

From HaskellWiki

< Performance
Revision as of 05:01, 21 July 2006 by Mwc (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Haskell Performance Resource

Constructs:
Data Types - Functions
Overloading - FFI - Arrays
Strings - Integers - I/O
Floating point - Concurrency
Modules - Monads

Techniques:
Strictness - Laziness
Avoiding space leaks
Accumulating parameter

Implementation-Specific:
GHC - nhc98 - Hugs
Yhc - JHC

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