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.
What does the standard stateless functional view of algorithms mean?
algorithms;functional programming
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.