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.

Answer 2

Theoretical Answer

No, it does not run in O(d) time. Its asymptotic performance is dominated by the the Integer subtraction d-1, which takes O(log d) time. This is repeated O(d) times, giving an asymptotic upper bound on time of O(d log d).

This upper bound can improve if you use an Integer representation with an asymptotically optimal O(1) decrement. In practice we don't, since the asymptotically optimal Integer implementations are slower even for unimaginably large values.

Practically the Integer arithmetic will be a small part of the running time of the program. For practical "large" depths (smaller than a machine word) the program's running time will be dominated by allocating and populating memory. For larger depths you will exhaust the resources of the computer.

Practical Answer

Ask the run time system's profiler.

In order to profile your code, we first need to make sure it is run. Haskell is lazily evaluated, so, unless we do something to cause the tree to be completely evaluated, it might not be. Unfortunately, completely exploring the tree will take O(2^d) steps. We could avoid forcing nodes we had already visited if we kept track of their StableNames. Fortunately, traversing a structure and keeping track of visited nodes by their memory locations is already provided by the data-reify package. Since we will be using it for profiling, we need to install it with profiling enabled (-p).

cabal install -p data-reify

Using Data.Reify requires the TypeFamilies extension and Control.Applicative.

{-# LANGUAGE TypeFamilies #-}

import Data.Reify
import Control.Applicative

We reproduce your Tree code.

data Tree a = Empty | Node a (Tree a) (Tree a)

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

Converting data to a graph with data-reify requires that we have a base functor for the data type. The base functor is a representation of the type with explicit recursion removed. The base functor for Tree is TreeF. An additional type parameter is added for the representation of recursive occurrence of the type, and each recursive occurrence is replaced by the new parameter.

data TreeF a x = EmptyF | NodeF a x x
    deriving (Show)

The MuRef instance required by reifyGraph requires that we provide a mapDeRef to traverse the structure with an Applicative and convert it to the base functor . The first argument provided to mapDeRef, which I have named deRef, is how we can convert the recursive occurrences of the structure.

instance MuRef (Tree a) where
    type DeRef (Tree a) = TreeF a
    mapDeRef deRef Empty        = pure EmptyF
    mapDeRef deRef (Node a l r) = NodeF a <$> deRef l <*> deRef r

We can make a little program to run to test the complete function. When the graph is small, we'll print it out to see what's going on. When the graph gets big, we'll only print out how many nodes it has.

main = do
    d <- getLine
    let (Just tree) = complete 0 (read d)
    graph@(Graph nodes _) <- reifyGraph tree
    if length nodes < 30 
    then print graph
    else print (length nodes)

I put this code in a file named profileSymmetricTree.hs. To compile it, we need to enable profiling with -prof and enable the run-time system with -rtsopts.

ghc -fforce-recomp -O2 -prof -fprof-auto -rtsopts profileSymmetricTree.hs

When we run it, we'll enable the time profile with the +RTS option -p. We'll give it the depth input 3 for the first run.

profileSymmetricTree +RTS -p
3
let [(1,NodeF 0 2 2),(2,NodeF 0 3 3),(3,NodeF 0 4 4),(4,EmptyF)] in 1

We can already see from the graph that the nodes are being shared between the left and right sides of the tree.

The profiler makes a file, profileSymmetricTree.prof.

                                                                                individual     inherited
COST CENTRE                        MODULE                     no.     entries  %time %alloc   %time %alloc

MAIN                               MAIN                        43           0    0.0    0.7   100.0  100.0
 main                              Main                        87           0  100.0   21.6   100.0   32.5
  ...
  main.(...)                       Main                        88           1    0.0    4.8     0.0    5.1
   complete                        Main                        90           1    0.0    0.0     0.0    0.3
    complete.complete'             Main                        92           4    0.0    0.2     0.0    0.3
     complete.complete'.copiedTree Main                        94           3    0.0    0.1     0.0    0.1

It shows in the entries column that complete.complete' was executed 4 times, and the complete.complete'.copiedTree was evaluated 3 times.

If you repeat this experiment with different depths, and plot the results, you should get a good idea what the practical asymptotic performance of complete is.

Here are the profiling results for a much greater depth, 300000.

                                                                                individual     inherited
COST CENTRE                        MODULE                     no.     entries  %time %alloc   %time %alloc

MAIN                               MAIN                        43           0    0.0    0.0   100.0  100.0
 main                              Main                        87           0    2.0    0.0    99.9  100.0
  ...
  main.(...)                       Main                        88           1    0.0    0.0     2.1    5.6
   complete                        Main                        90           1    0.0    0.0     2.1    5.6
    complete.complete'             Main                        92      300001    1.3    4.4     2.1    5.6
     complete.complete'.copiedTree Main                        94      300000    0.8    1.3     0.8    1.3