Function to Populate Tree in O(depth)

Question

Purely Functional Data Structures has the following exercise:

-- 2.5 Sharing can be useful within a single object, not just between objects.
-- For example, if the two subtress of a given node are identical, then they can 
-- be represented by the same tree.
-- Part a: make a `complete a Int` function that creates a tree of 
-- depth Int, putting a in every leaf of the tree.
complete :: a -> Integer -> Maybe (Tree a)
complete x depth 
 | depth < 0  = Nothing
 | otherwise  = Just $ complete' depth
                        where complete' d 
                                | d == 0    = Empty
                                | otherwise = let copiedTree = complete' (d-1) 
                                              in Node x copiedTree copiedTree

Does this implementation run in O(d) time? Could you please say why or why not?

Answer 1

The interesting part of the code is the complete' function:

complete' d 
  | d == 0    = Empty
  | otherwise = let copiedTree = complete' (d-1) 
                in Node x copiedTree copiedTree

As Cirdec's answer suggests, we should be careful to analyze each part of the implementation to make sure our assumptions are valid. As a general rule, we can assume that the following take 1 unit of time each*:

1. Using a data constructor to construct a value (e.g., using Empty to make an empty tree or using Node to turn a value and two trees into a tree).

2. Pattern matching on a value to see what data constructor it was built from and what values the data constructor was applied to.

3. Guards and if/then/else expressions (which are implemented internally using pattern matching).

4. Comparing an Integer to 0.

Cirdec mentions that the operation of subtracting 1 from an Integer is logarithmic in the size of the integer. As they say, this is essentially an artifact of the way Integer is implemented. It is possible to implement integers so that it takes only one step to compare them to 0 and also takes only one step to decrement them by 1. To keep things very general, it's safe to assume that there is some function c such that the cost of decrementing an Integer is c(depth).

---

Now that we've taken care of those preliminaries, let's get down to work! As is generally the case, we need to set up a system of equations and solve it. Let f(d) be the number of steps needed to calculate complete' d. Then the first equation is very simple:

f(0) = 2

That's because it costs 1 step to compare d to 0, and another step to check that the result is True.

The other equation is the interesting part. Think about what happens when d > 0:

1. We calculate d == 0.
2. We check if that is True (it's not).
3. We calculate d-1 (let's call the result dm1)
4. We calculate complete' dm1, saving the result as copiedTree.
5. We apply a Node constructor to x, copiedTree, and copiedTree.

The first part takes 1 step. The second part takes one step. The third part takes c(depth) steps, and the fifth step takes 1 step. What about the fourth part? Well, that takes f(d-1) steps, so this will be a recursive definition.

f(0) = 2
f(d) = (3+c(depth)) + f(d-1)    when d > 0

OK, now we're cooking with gas! Let's calculate the first few values of f:

f(0) = 2
f(1) = (3+c(depth)) + f(0) = (3+c(depth)) + 2
f(2) = (3+c(depth)) + f(1)
     = (3+c(depth)) + ((3+c(depth)) + 2)
     = 2*(3+c(depth)) + 2
f(3) = (3+c(depth)) + f(2)
     = (3+c(depth)) + (2*(3+c(depth)) + 2)
     = 3*(3+c(depth)) + 2

You should be starting to see a pattern by now:

f(d) = d*(3+c(depth)) + 2

We generally prove things about recursive functions using mathematical induction.

Base case:

The claim holds for d=0 because 0*(3+c(depth))+2=0+2=2=f(0).

Suppose that the claim holds for d=D. Then

f(D+1) = (3+c(depth)) + f(D)
       = (3+c(depth)) + (D*(3+c(depth))+2)
       = (D+1)*(3+c(depth))+2

So the claim holds for D+1 as well. Thus by induction, it holds for all natural numbers d. As a reminder, this gives the conclusion that complete' d takes

f(d) = d*(3+c(depth))+2

time. Now how do we express that in big O terms? Well, big O doesn't care about the constant coefficients of any of the terms, and only cares about the highest-order terms. We can safely assume that c(depth)>=1, so we get

f(d) ∈ O(d*c(depth))

Zooming out to complete, this looks like O(depth*c(depth))

If you use the real cost of Integer decrement, this gives you O(depth*log(depth)). If you pretend that Integer decrement is O(1), this gives you O(depth).

Side note: As you continue to work through Okasaki, you will eventually reach section 10.2.1, where you will see a way to implement natural numbers supporting O(1) decrement and O(1) addition (but not efficient subtraction).

* Haskell's lazy evaluation keeps this from being precisely true, but if you pretend that everything is evaluated strictly, you will get an upper bound for the true value, which will be good enough in this case. If you want to learn how to analyze data structures that use laziness to get good asymptotic bounds, you should keep reading Okasaki.