In the above Queen example, the locations of a Queen object and its Worker objects are subject to change. Every time a Worker ant moves its Queen, it has the side effect of changing the Queen's origin. The Queen object remains the "same". This seems like a reasonable thing to have. In the functional programming paradigm, to move the Queen, the Worker ant would have to instantiate a new Queen object with a new location and find a way to associate itself to this new Queen, which does not seem to model the "real" ant world very well. By allowing our objects to change their internal states in appropriate situations, our programming model becomes more "realistic", more efficient, and in many cases "simpler".
To further illustrate the relevance of state changes, consider the problem of moving the minimum element of a list of integers to the front of the list. Since the current IList model is immutable, we can only solve the problem by returning a copy of the original list with its minimum at the front. Below is an algorithm to solve the problem that makes use of an accumulator to accumulate the current minimum and internally updates it as the list is being traversed.
The list is assumed to hold no duplicate values.
Min2Front.java
public class Min2Front implements IListAlgo { private Integer _accMin; // accumulated min. private IListFactory _fact; public Min2Front(IListFactory f) { _fact = f; } public Object emptyCase(IMTList mtHost, Object... nu) { return mtHost; } public Object nonEmptyCase(INEList neHost, Object... nu) { // We assign _accMin the first of L as a candidate for minimum: _accMin = (Integer)neHost.getFirst(); /** * Let us consider the set S of all elements in L that precede L. * S is clearly empty. At this point we have established the following: * _accMin is an element of L and is smaller than all elements of S. * We now call on an anonymous helper to operate on L in order to find * the minimum and remove it from L. This helper will recursively * travese L to the end in order to obtain the minimum, save it in * _accMin and reconstruct the host list L without the minimum on its way * back from the recursive list traversal. */ IList withoutMin = (IList)neHost.execute(new IListAlgo() { /** * Note: when L executes this helper, this case is called since L is * not empty. Thus for the first call to this method, h is L. * We update accMin to ensure that it is an element of L and is the * minimum of all elements in L that precedes the rest of the host * parameter h. Then we recursively call this helper on h.getRest() * to save the minimum in _accMin and create a copy of h.getRest() * that does not contain _accMin. */ public Object nonEmptyCase(INEList h, Object... nu) { if ((Integer)h.getFirst() < accMin) {_accMin = first; } /** * At this point, we have established the following invariant: * _accMin is an element of L and is the minimum of all elements * in L that precedes h.getRest(). */IList accList = (IList)h.getRest().execute(this, null); /** * By induction, _accMin is now the minimum of the whole outer * host list L, and accList is a copy of h.getRest() that does * not contain _accMin. */ if (!first.equals(_accMin)) { accList = _fact.makeNEList(first, accList); }
In the above, the comments are longer than the code. The above code and comments can be greatly simplified if the list is mutable. What does it mean for a list to be mutable?
- 瀏覽次數：1748
