# Elements of Programming: Transformations and Their Orbits

• Print
This chapter is from the book

## 2.5 Actions

Algorithms often use a transformation f in a statement like

`x = f(x);`

Changing the state of an object by applying a transformation to it defines an action on the object. There is a duality between transformations and the corresponding actions: An action is definable in terms of a transformation, and vice versa:

```void a(T& x) { x = f(x); }   // action from transformation

and

T f(T x) { a(x); return x; } // transformation from action
```

Despite this duality, independent implementations are sometimes more efficient, in which case both action and transformation need to be provided. For example, if a transformation is defined on a large object and modifies only part of its overall state, the action could be considerably faster.

#### Exercise 2.6.

Rewrite all the algorithms in this chapter in terms of actions.

#### Project 2.1.

Another way to detect a cycle is to repeatedly test a single advancing element for equality with a stored element while replacing the stored element at ever-increasing intervals. This and other ideas are described in Sedgewick, et al. [1979], Brent [1980], and Levy [1982]. Implement other algorithms for orbit analysis, compare their performance for different applications, and develop a set of recommendations for selecting the appropriate algorithm.