38
$\begingroup$

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?

Improve this question
$\endgroup$
11
  • 3
    $\begingroup$ This might be what you're looking for. $\endgroup$
    – Aristu
    Apr 25, 2017 at 3:26
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Apr 25, 2017 at 7:01
  • 3
    $\begingroup$ 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). $\endgroup$
    – Tanner Swett
    Apr 25, 2017 at 11:28
  • 1
    $\begingroup$ @BobJarvis Depends. Is a list an abstract datatype for you, or are you specifically considering linked lists? $\endgroup$
    – Raphael ♦
    Apr 25, 2017 at 16:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – Cort Ammon
    Apr 25, 2017 at 17:05

3 Answers 3

Reset to default
34
$\begingroup$

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.

Improve this answer
$\endgroup$
23
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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) $\endgroup$
    – Paul Draper
    Apr 26, 2017 at 21:34
  • 3
    $\begingroup$ @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. $\endgroup$
    – Raphael ♦
    Apr 26, 2017 at 21:46
  • $\begingroup$ that sounds an awful lot like "get rid of the machine model" $\endgroup$
    – Paul Draper
    Apr 29, 2017 at 6:50
  • $\begingroup$ @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. $\endgroup$
    – Raphael ♦
    Apr 29, 2017 at 8:07
1
$\begingroup$

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).

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.