Calculating work done by f x = (x,x)

Question

Let's say I have this function: (Haskell syntax)

f x = (x,x)

What is the work (amount of calculation) performed by the function?

At first I thought it was obviously constant, but what if the type of x is not finite, meaning, x can take an arbitrary amount of memory? One would have to take into account the work done by copying x as well, right?

This led me to believe that the work done by the function is actually linear in the size of the input.

This isn't homework for itself, but came up when I had to define the work done by the function:

f x = [x]

Which has a similar issue, I believe.

Answer 1

Very informally, the work done depends on your language's operational semantics. Haskell, well, it's lazy, so you pay only constant factors to:

• push pointers to x on the stack
• allocate a heap cell for (,)
• apply (,) to its arguments
• return a pointer to the heap cell

Done. O(1) work, performed when the caller looks at the result of f.

Now, you will trigger further evaluation if you look inside the (,) -- and that work is dependent on the work to evaluate x itself. Since in Haskell the references to x are shared, you evaluate it only once.

So the work in Haskell is O(work of x) if you fully evaluate the result. Your function f only adds constant factors.

Answer 2

Chris Okasaki has a wonderful method of determining the work charged to function call when some (or total) laziness is introduced. I believe it is in his paper on Purely Functional Data Structures. I know it is in the book version -- I read that part of the book last month. Basically you charge a constant factor for the promise/thunk created, charge nothing for evaluating any passed in promises/thunks (assume they've already been forced / are in normal form [not just WHNF]). That's an underestimate. If you want an overestimate charge also the cost of forcing / converting to normal form each promise / thunk created by the function. At least, that's how I remember it in my extremely tired state.

Look it up in Okasaki: http://www.westpoint.edu/eecs/SitePages/Chris%20Okasaki.aspx#thesis -- I swear the thesis used be be downloadable.