20.4.1 Solve a more general problem first

The first strategy is to solve a more general problem first. That is, we solve a “harder” problem than the specific problem at hand, then use the solution of the “harder” problem to get the specific solution desired.

Sometimes a solution of the more general problem is actually easier to find because the problem is simpler to state, more symmetrical, or less obscured by special conditions. The general solution can often be used to solve other related problems.

Often the solution of the more general problem can actually lead to a more efficient solution of the specific problem.

Examples

We have already seen one example of this technique: finding the first occurrence of an item in a list in Chapter 18.

First, we devised a program to find all occurrences in a list. Then we selected the first occurrence from the set of all occurrences. (Lazy evaluation of Haskell programs means that this use of a more general solution differs very little in efficiency from a specialized version.)

We have also seen several cases where we have generalized problems by adding one or more accumulating parameters. These “harder” problems can lead to more efficient tail recursive solutions.

For example, consider the tail recursive Fibonacci program we developed in Chapter 9. We added two extra arguments to the function.

    fib2 :: Int -> Int
    fib2 n | n >= 0 = fibIter n 0 1 
        where 
            fibIter 0 p q         = p
            fibIter m p q | m > 0 = fibIter (m-1) q (p+q)

Another approach is to use the tupling technique. Instead of adding extra arguments, we add extra results.

For example, in the Fibonacci program fastfib below, we compute (fib n, fib (n+1)) instead of just fib n. This is a harder problem, but it actually gives us more information to work with and, hence, provides more opportunity for optimization. (We formally derive this solution in Chapter 26.)

    fastfib :: Int -> Int
    fastfib n | n >= 0 = fst (twofib n)

    twofib :: Int -> (Int,Int) 
    twofib 0 = (0,1) 
    twofib n = (b,a+b) 
        where (a,b) = twofib (n-1)

20.4.2 Solve a simpler problem first

The second strategy is to solve a simpler problem first. After solving the simpler problem, we then adapt or extend the solution to solve the original problem.

Often the mass of details in a problem description makes seeing a solution difficult. In the previous technique we made the problem easier by finding a more general problem to solve. In this technique, we move in the other direction: we find a more specific problem that is similar and solve it.

At worst, by solving the simpler problem we should get a better understanding of the problem we really want to solve. The more familiar we are with a problem, the more information we have about it, and, hence, the more likely we will be able to solve it.

At best, by solving the simpler problem we will find a solution that can be easily extended to build a solution to the original problem.

Examples

Consider a program to convert a positive integer of up to six digits to a string consisting of the English words for that number. For example, 369027 yields the string:

    three hundred and sixty-nine thousand and twenty-seven

To deal with the complexity of this problem, we can work as follows:

1. Solve the problem of converting a two-digit number to words. (The single digit numbers and numbers in teens are special cases.)
2. Then extend the two-digit solution to three digits. (This can basically use the solution to part “a” twice.)
3. Then extend three-digit solution to to six digits. (This can basically use the solution to part “b” twice.)

See Section 4.1 of the classic Bird and Wadler textbook [1] for the details of this problem and a solution.

TODO: May want to create some code for this problem rather than just refer to an old textbook.

The process of generalizing first-order functions into higher-order functions is another example of this “solve a simpler problem first” strategy. Recall how we motivated the development of the higher-order library functions such as map, filter, and foldr in Chapter 15. Also consider the function generalization approach used in the cosequential processing case study in Chapter 19.

20.4.3 Reuse off-the-shelf solutions to standard subproblems

The third strategy is to reuse an off-the-shelf solutions to a standard subproblem.

We have been doing this all during this semester, especially since we began began studying polymorphism and higher-order functions.

The basic idea is to identify standard patterns of computation (e.g., standard Prelude functions such as length, take{.haskell, zip{.haskell, map{.haskell, filter{.haskell, foldr{.haskell) that will solve some aspects of the problem and then combine (e.g., using function composition) these standard patterns with your own specialized functions to construct a solution to the problem.

Examples

We have seen several examples of this technique in this textbook and its exercises.

See section 4.2 of the classic Bird and Wadler textbook [1] for a case study that develops a package of functions to do arithmetic on variable length integers. The functions take advantage of several of the standard Prelude functions.

20.4.4 Solve a related problem

The fourth strategy is to solve a related problem. After solving the related problem, we then transform the solution of the related problem to get a solution to the original problem.

Perhaps we can find an entirely different problem formulation (i.e., stated in different terms) for which we can readily find a solution. Then that solution can be converted into a solution to the problem at hand.

Examples

For example, we can recast a problem in terms of mathematical or logical frameworks (e.g., sets, relations, graphs, finite state machines, grammars, algebraic structures, differential equations, etc.), solve the corresponding problem in those terms, and then interpret the result for the original problem. The simplification provided by the frameworks may reveal solutions that are obscured in the details of the problem. We can also take advantage of the theory and techniques that have been found previously for the mathematical frameworks.

Consider the problem of breaking a string of text into the list of its component lines.

This is not trivial. However, the “inverse” problem is trivial. All that is needed to convert a list of lines to a string of text is to insert linefeed characters between the lines.

We can first solve the inverse problem (line-folding) and then use it to calculate what the line-breaking program must be. (See Section 4.3 of the Bird and Wadler textbook [1] and a Chapter 27 in this textbook.)

20.4.5 Separate concerns

The fifth strategy is to separate concerns. That is, we partition the problem into logically separate problems, solve each problem separately, then combine the solutions to the subproblems to construct a solution to the problem at hand.

As we have seen in the above strategies, when a problem is complex and difficult to attack directly, we search for simpler, but related, problems to solve, then build a solution to the complex problem from the simpler problems.

Examples

We have seen examples of this approach in earlier chapters and homework assignments. We separated concerns when we used stepwise refinement to develop a square root function, data abstraction in the rational number case study, and function pipelines.

Consider the development of a program to print a calendar for any year in various formats. We can approach this problem by first separating it into two independent subproblems:

1. building a calendar
2. formatting the output

After solving each of these simpler problems, the more complex problem can be solved easily by combining the two solutions. (See Section 4.5 of the classic Bird and Wadler textbook [1] for the details of this problem and a solution.)

20.4.6 Divide and conquer

The sixth strategy is divide and conquer. This is a special case of the “solve a simpler problem first” strategy. In this technique, we must divide the problem into subproblems that are the same as the original problem except that the size of the input is smaller.

This process of division continues recursively until we get a problem that can be solved trivially, then we combined we reverse the process by combining the solutions to subproblems to form solutions to larger problems.

Examples

Examples of divide and conquer from earlier chapters include the logarithmic exponentiation function expt3 in Chapter 9 and the merge sort function msort in Chapter 17.

Another common example of the divide and conquer approach is binary search. (See Section 6.4.3 of the classic Bird and Wadler textbook [1].)

Chapter 17 examines divide and conquer algorithms in terms of a higher order function that captures the pattern.

There are, of course, other strategies that can be used to approach problem solving.