How to find time complexity for functions in lazy functional languages?
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. 864
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? 904