How is algorithm complexity modeled for functional languages?

Algorithm complexity is designed to be independent of lower level details but it is based on an imperative model, e.g. array access and modifying a node in a tree take O(1) time. This is not the case in pure functional languages. The Haskell list takes linear time for access. Modifying a node in a tree involves making a new copy of the tree.

Should then there be an alternate modeling of algorithm complexity for functional languages?

• This might be what you're looking for. Apr 25 '17 at 3:26
• Your question might be answered here: cs.stackexchange.com/q/18262/755. In particular, the time complexity in a purely function language differs from the time complexity in an imperative language by at most a ratio of $O(\log n)$, for some suitable assumptions on the capabilities of both languages.
– D.W.
Apr 25 '17 at 7:01
• GHC Haskell supports mutable arrays and trees and whatnot, allowing you to do array access and modify tree nodes in O(1) time, using "state threads" (the ST monads). Apr 25 '17 at 11:28
• @BobJarvis Depends. Is a list an abstract datatype for you, or are you specifically considering linked lists?
– Raphael
Apr 25 '17 at 16:00
• What purpose do you seek for modeling algorithmic complexity? Are you looking for something that is mathematically pure, or something that is practical? For a practical value, it should pay attention to things like whether or not you have memorization available to you, but from a mathematical purist point of view, the capabilities of the implementation should not matter. Apr 25 '17 at 17:05

If you assume that the $\lambda$-calculus is a good model of functional programming languages, then one may think: the $\lambda$-calculus has a seemingly simple notion of time-complexity: just count the number of $\beta$-reduction steps $(\lambda x.M)N \rightarrow M[N/x]$.

But is this a good complexity measure?

To answer this question, we should clarify what we mean by complexity measure in the first place. One good answer is given by the Slot and van Emde Boas thesis: any good complexity measure should have a polynomial relationship to the canonical notion of time-complexity defined using Turing machines. In other words, there should be a 'reasonable' encoding $tr(.)$ from $\lambda$-calculus terms to Turing machines, such for some polynomial $p$, it is the case that for each term $M$ of size $|M|$: $M$ reduces to a value in $p(|M|)$ $\beta$-reduction steps exactly when $tr(M)$ reduces to a value in $p(|tr(M)|)$ steps of a Turing machine.

For a long time, it was unclear if this can be achieved in the λ-calculus. The main problems are the following.

• There are terms that produce normal forms (in a polynomial number of steps) that are of exponential size. Even writing down the normal forms takes exponential time.
• The chosen reduction strategy plays an important role. For example there exists a family of terms which reduces in a polynomial number of parallel β-steps (in the sense of optimal λ-reduction), but whose complexity is non-elementary (meaning worse then exponential).

The paper "Beta Reduction is Invariant, Indeed" by B. Accattoli and U. Dal Lago clarifies the issue by showing a 'reasonable' encoding that preserves the complexity class P of polynomial time functions, assuming leftmost-outermost call-by-name reductions. The key insight is the exponential blow-up can only happen for 'uninteresting' reasons which can be defeated by proper sharing. In other words, the class P is the same whether you define it counting Turing machine steps or (leftmost-outermost) $\beta$-reductions.

I'm not sure what the situation is for other evaluation strategies. I'm not aware that a similar programme has been carried out for space complexity.

Algorithm complexity is designed to be independent of lower level details.

No, not really. We always count elementary operations in some machine model:

• Steps for Turing machines.
• Basic operations on RAMs.

You were probably thinking of the whole $\Omega$/$\Theta$/$O$-business. While it's true that you can abstract away some implementation details with Landau asymptotics, you do not get rid of the impact of the machine model. Algorithms have very different running times on, say TMs and RAMs -- even if you consider only $\Theta$-classes!

Therefore, your question has a simple answer: fix a machine model and which "operations" to count. This will give you a measure. If you want results to be comparable to non-functional algorithms, you'd be best served to compile your programs to RAM (for algorithm analysis) or TM (for complexity theory), and analyze the result. Transfer theorems may exist to ease this process.

• Agreed. Side note: People do frequently make a lot of mistakes about what operations are "constant". E.g. assuming a + b is O(1) when it is really O(log ab) Apr 26 '17 at 21:34
• @PaulDraper That's a different assumption, not necessarily a mistake. We can model what we want -- the question is if it answers interesting questions. See also here.
– Raphael
Apr 26 '17 at 21:46
• that sounds an awful lot like "get rid of the machine model" Apr 29 '17 at 6:50
• @PaulDraper Depends on what kind of sentiments you attach to the word "machine". See also this discussion. FWIW, the unit-cost RAM model -- arguably the standard model in algorithm analysis! -- is useful, otherwise it wouldn't have been used for decades now. All the familiar bounds for sorting, search tress, etc. are based on that model. It makes sense because it models real computers well as long as the numbers fit in registers.
– Raphael
Apr 29 '17 at 8:07

Instead of formulating your complexity measure in terms of some underlying abstract machine, you can bake cost into the language definitions itself - this is called a Cost Dynamics. One attaches a cost to every evaluation rule in the language, in a compositional manner - that is, the cost of an operation is a function of the cost of its sub-expressions. This approach is most natural for functional languages, but it may be used for any well-defined programming language (of course, most programming languages are unfortunately not well-defined).