Intro Lecture

We'll start by defining an insertion function, which places an element x into a list in the right ordering; we can assume the list ys is already sorted.

1-- pre: list is ordered
2insert :: Ord a => a -> [a] -> [a]
3insert x [] = [x]
4insert x (y:ys)
5  | x <= y    = x : y : ys
6  | otherwise = y : insert x ys

1. Algorithm Cost

A big part of algorithm design, is understanding how long a function takes to execute. For now, we'll use our intuition. Later, we'll have a more precise way of establishing a function's cost.

This is an open form function, but we prefer a closed form function. We can solve this by expanding the function:

Using insert, we can define the insertion sort algorithm:

1isort :: Ord a => [a] -> [a]
2isort [] = []
3isort (x:xs) = insert x (isort xs)

2. Normal Forms

Lazy things are in WHNF (Weak Head Normal Form), strict things are in NF (Normal Form). This is usually defined in terms of lambda calculus:

An expression e is in normal form if it takes the form:

WNHF is similar but lambda bodies need not be normal. For example, \x -> (\y -> y) x is in WHNF but not NF.

3. Cost Measure

Let's define a concrete measure of cost. Expressions are formed as follows:

1e, e1, e2 ::= x                    -- variable
2            | k                    -- constant (0, [], (:), +, *, null)
3            | f e1 .. en           -- application
4            | if e then e1 else e2 -- conditional

Functions will always have the form:

f x1 .. xn = e

We can translate our function into this language:

1insert x xs =
2  if null xs then x : []
3  else if x <= head xs then x : xs
4  else head xs : insert x (tail xs)

Now, we can give a concrete cost-semantic to our language:

In other words, our own defined functions cost 1 for the call, then the cost of the body.

1T(x) = 0  -- in other words, variables are free
2T(k) = 0  -- in other words, constants are free
3-- evaluating an application is the same as evaluating all the arguments,
4-- and then the application of `f` to those arguments (as above)
5T(f e1 .. en) = T(f) e1 .. en + T(e1) + .. + T(en)
6-- evaluating a condition first evaluates the condition, then conditonally
7-- evaluates either arm of the conditional.
8T(if e then e1 else e2) = T(e) + if e then T(e1) else T(e2)

4. Case Study: length

Let's try to find the cost of the length function:

length xs = if null xs then 0 else 1 + length (tail xs)
1T(length xs)
2= -- by T(f e1 .. en) = T(f) e1 .. en + T(e1) + .. + T(en)
3T(length) xs + T(xs)
4= -- by T(x) = 0
5T(length) xs + 0
6= -- by T(f) x1 .. xn = 1 + T(e)
71 + T(if null xs then 0 else 1 + length (tail xs))
8= -- by T(if e then e1 else e2) = T(e) + if e then T(e1) else T(e2)
91 + T(null xs) + if null xs then T(0) else T(length (tail xs))
10= -- by T(f e1 .. en) = T(f) e1 .. en + T(e1) + .. + T(en)
111 + T(null) xs + T(xs) + if null xs then T(0) else T(length (tail xs))
12= -- By T(primitive) = 0, T(x) = 0
131 + 0 + 0 + if null xs then T(0) else T(length (tail xs))
14= -- By T(k) = 0
151 + if null xs then 0 else T(length (tail xs))
16= -- By T(f e1 .. en) = T(f) e1 .. en + T(e1) + .. + T(en)
171 + if null xs then 0 else T(length) (tail xs) + T(tail xs)
18= -- By T(f e1 .. en) = T(f) e1 .. en + T(e1) + .. + T(en)
191 + if null xs then 0 else T(length) (tail xs) + T(tail) xs + T(xs)
201 + if null xs then 0 else T(length) (tail xs) + 0 + 0
21= -- simplify
221 + if null xs then 0 else T(length) (tail xs)

At this point, we can stop, as we are back in terms of just an evaluation of ourselves. This worked out, but was very long-winded and the language is not particularly fun to work with. As such, the key take-home from this exercise is to notice that cost is going to be introduced by a call to our "own" functions. Calls out to primitives (which here are representing pattern matching too) are considered free.

As one last note, though, we can apply some rules to provide a shortcut for looking at how to cost-model composition of functions:

5. Complexity Classes

We can define some means of computing functions by considering their ratios:

With these comparisons defined, we can define complexity classes:

Alternatively, you may find it easier to understand as self-theoretic:

Back to Home