Calculating work done by f x = (x,x)
asymptotic-complexity, functional-programming, haskell
Solution
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.
Problem
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.