How to find time complexity for functions in lazy functional languages?

Question

So far, I have looked around the internet for information how to find the time complexity for functions in lazy functional languages, but most of the resources on time complexity focus on strict imperative languages, and there seems to be very little about finding time complexity in lazy functional languages.

The former resources are somewhat unsuitable for finding the time complexity of lazy functions. E.g.:

minimum = head . sort

For a good definition of sort, minimum will run in $\cal{O}(n)$ time even though head runs in $\cal{O}(1)$ time and sort can run in $\cal{O}(n * log(n))$ or $\cal{O}(n^2)$ time.

However if I wrote this function in a strict imperative language as

fun minimum(list):
    sort(list);
    return head(list);

and then tried to combine the complexities of the sort and head functions the way it is done with algorithms in strict imperative languages, then I would get that the minimum function will run in $\cal{O}(n * log(n)) + \cal{O}(1) = \cal{O}(n * log(n))$ or $\cal{O}(n^2) + \cal{O}(1) = \cal{O}(n^2)$ time.

Which is of course correct for the strict function, however it doesn't have to be very accurate for the lazy version of the same function as shown above. So using the same technique in lazy programming languages wouldn't be all that useful.

I think the difference comes in from the laziness, because it causes data to be computed only as much as they are required by the function using them. This is opposite to how it works in strict languages, where the function using the data has no control over how much the data gets evaluated by the function creating them.

This means that knowing the time complexity of fully evaluating a function, which is what one usually looks for when figuring out the time complexity of a function, isn't necessarily useful for knowing the time complexity of a function using data from this function unless said function evaluates the data fully.

So what is useful to know about one function to figure out the time complexity of another function using the resulting data from it inside a lazy functional language?

Is there a formal system that helps out with finding out the time complexity in this situation?

I know I could probably try evaluating the whole function by hand if I have source to all the functions that it uses, but I don't necessarily have that.

On similar note, if I don't have the source of a function and I only have a documentation to it, then what would the writer of said documentation need to include in the documentation for me to be able to accurately find the time complexity of a function that uses their function?

As said before, the time complexity of evaluating the function fully isn't enough. But what if they included time complexity of evaluating the first i elements of the list the function is generating? Would that be enough? If yes, then how could this be generalized to other data structures as well?

Answer 1

I would consider an approach based on potential. Note that lazy evaluation changes the internal state of an object and therefore takes away an important advantage of functional programming.

As an example, imagine the following three functions

• sort : List $\rightarrow$ List. Sorts the list using Selection Sort.
• unique_special : List $\rightarrow$ List. For every odd position $i$ in the input list, the element at that position is removed from the list if it is equal to the element at $i+1$.
• head : List $\rightarrow$ X. Finds the first element of the list.

Given a list $L$, I will use $\Phi(L)$ for its potential. $\Phi(L) : \{1, \dots, |L|\} \rightarrow \mathbb{N}$ is a function describing the cost of each element.

A "clear" list has a constant potential, i.e. $\Phi(L)(i) = 1$ for all indices $i$.

Let L be a list and sort(L) = L'. Then $\Phi(L')(i) = \sum\limits_{j=1}^{|L|} \Phi(L)(j)$, because Selection Sort will have to look at every element in $L$ to find a minimal one. After this, $L$ is completely evaluated, i.e. it is not "lazy" anymore. This means the potential of every element is reduced to $\Phi(L)(i) = 1$. Here you can see the importance of the fact, that lazy evaluation can change within an object. If you assume that is not possible, for example by disallowing variables (e.g. via "where" in Haskell), the analysis becomes easier.

For unique_special, consider again L' = unique_special(L). To evaluate the first element, the next one has to be evaluated as well (to compare them). $\Phi(L')(1) = \Phi(L)(1) + \Phi(L)(2)$. Of course, would $L'(1)$ be evaluated, the potential of $L(1)$ and $L(2)$ would become 1.

Later elements require additional knowledge of whether the previous elements were deleted. You have $L'(2) = L(1)$ if the first element was deleted and $L'(2) = L(2)$ otherwise. Hence, $\Phi(L')(2) = \Phi(L)(1) + \Phi(L)(2)$ and $\Phi(L')(3) = \Phi(L)(1) + \Phi(L)(2) + \Phi(L)(3) + \Phi(L)(4)$.

Generalizing this formula results in $\Phi(L')(i) = \sum\limits_{j=1}^k \Phi(L)(j)$, where $k = \lfloor \frac{i}{2} \rfloor \cdot 2$.

Finally, consider head(L). This does not create a new list, it just requires you to pay the potential of $\Phi(L)(1)$.

As you can see, this clearly increases the complexity of function definitions, especially if you want to include changing potential of the same data structure in your analysis. It gives you the opportunity for a more abstract analysis though:

Let $L$ be a completely evaluated / non-lazy list and the call head(sort(L))). The cost of this call will be $\Phi(\text{sort}(L))(1) = \sum\limits_{j=1}^{|L|} \Phi(L)(j) = |L|$.

A second example: What is the cost of the call head(unique_special(L')), where $L' = \text{sort}(L)$?

\begin{align*} & \Phi(\text{unique_special}(L'))(1) \\ =& \Phi(L')(1) + \Phi(L')(2) \\ =& \sum\limits_{j=1}^{|L|} 1 + \sum\limits_{j=1}^{|L|} 1 \\ =& 2 |L| \end{align*}

You can put more detail into the description of $\Phi$ to observe more accurate results.

Regarding generalization to other data structures, I didn't think about that too much so far. It should be clear that similar structures such as queues work in a similar way. However, for example for a Union-Find structure, I can't think of a way my approach would give you any advantage.

An addition regarding non-linear data structures, for example binary search trees. While it is the easiest option, there is no definite need to use a set $\{1, \dots, n\}$ as the domain of $\Phi$. A common way to index the nodes of a binary tree is to use strings in $\{0,1\}^*$. The root is labelled with the empty string $\varepsilon$ and for a node $v$, the left successor is $v0$ and the right successor is $v1$. For example, the following tree

   5
 4   8
1   6 9

would have the domain $\{\varepsilon, 0, 00, 1, 10, 11\}$.

Imagine a function delete : Tree $\times$ Node $\rightarrow$ Tree to remove a certain node from the tree. You need to check if either of the subtrees is empty. Let delete($T$, $v$) = $T'$, then the potential is $\Phi(T')(v) = \sum\limits_{\substack{w \in \{0,1\}^* \\ w \text{ is a descendant of } v}} \Phi(T)(w)$, where we assume $\Phi(T)(w) = 0$ if $w$ is not a node of $T$.