6

From Kelvin Murphy's review on Algorithms (4th Edition) by Sedgewick and Wayne

For data structures, it is obviously natural to use classes, but they also adopt this approach for many algorithms, esp. graph processing ones. This allows the algo to do pre-processing and to store internal state, and then to provide a service to the caller. This is more general than the standard stateless functional view of algorithms.

  • What does the "stateless functional view of algorithms" mean?

  • The views I have read from some algorithm books are based on states of objects. So I think that the standard view of algorithms are based on states, correct?

Thanks.

14

What does the "stateless functional view of algorithms" mean?

We can think of an algorithm in the abstract as a description of a mechanism that takes certain inputs and produces certain outputs independent of the state of the world. If you have a mechanism called "sum" that takes in 2 and 3 and produces 5, it always produces 5 when given 2 and 3, no matter what the phase of the moon or who is the king of France today. There is no "state" that the algorithm must consult other than the values provided as arguments.

The distinction the author is drawing is that even in algorithms that are "pure" in this respect, it is often convenient to do some pre-processing, store that as state, and then use that state during the operation of an algorithm. Even if the result is an algorithm that appears to not depend on the state of the world, internally it is consuming or modifying its own private universe of state.

I think that the standard view of algorithms are based on states, correct?

The standard view of algorithms in OO or procedural languages is a sequence of mutations to state, yes. But that is not the standard functional view. The functional view is that algorithms have outputs that depend on inputs and there is no mutable state.

It is always possible to write a stateful algorithm as a stateless algorithm; you just make the state one of the inputs to the algorithm, and you make the outputs include a copy of "changes" to the state; nothing is actually mutated. But it is often inconvenient, inelegant or non-performant to do so in practice.

Of course the reverse is also true; many algorithms that are written as a sequence of mutations are vulnerable to nasty bugs where mutations are performed inconsistently or out of order. By rethinking an algorithm as a production of values from inputs with no mutations, you can often get significant performance wins (thanks to persistence, memoization, and so on) and remove sources of bugs.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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