Go to the first, previous, next, last section, table of contents.

Normal Form

The more information you have available, the simpler it is likely to be to solve the problem. Make sense? Extra information can't hurt, and may help.

You will often find that your first datastructure design contains unneeded degrees of freedom. If the problem to be solved is nontrivial, you may often make life much simpler by systematically eliminating those extra degrees of freedom before attempting a solution. This process is often called "reduction to a normal form". The result when done is that you know more about the datastructure, and so you have fewer cases to consider when coding, or more information available which you may take advantage of when coding the main case.

As a simple example, comparing two arrays of numbers to see if they contain the same set of numbers is fairly expensive. But if we sort each array first, it becomes fast and completely trivial to code.

Along the same lines, comparing two binary trees to see if they have the same leaves in the same order is a tricky problem in recursion, but becomes completely trivial if we first reduce each tree to a linear linklist.

As a more sophisticated example, when a symbolic algebra package attempts to check two expressions for equivalence, the task is considerably eased if each expression is first reduced to a standard form: Systematically applying this insight has led to significant advances in symbolic algebra systems.

Much of the front-end processing in a compiler can be understood as stripping out irrelevant degrees of freedom and massaging the input code into a normal form; significant parts of some dataflow analysis, code optimization, and code generation components of compilers can be similarly understood.

Taken to the extreme, as in Church's lambda calculus and the denotational semantics systems based on it, all computation can be understood as reduction to a normal form. But that overinflates the concept to uselessness for most practical purposes.

Learn to keep a critical eye cocked on your input, and to habitually look for ways to reduce it to a simpler form before beginning serious processing on it.

Go to the first, previous, next, last section, table of contents.