Let's finish up Mergesort with the merge function. Again, this is just recursively iterating through the two lists, which leads to the following algorithm.
(: merge (-> (Listof Integer) (Listof Integer) (Listof Integer)))
;; Combine two sorted lists into a single sorted list
(define (merge lst1 lst2)
(match* (lst1 lst2)
[(lst1 '()) lst1]
[('() lst2) lst2]
[((cons h1 t1) (cons h2 t2))
(if (< h1 h2)
(cons h1 (merge t1 lst2))
(cons h2 (merge lst1 t2)))]))
Note that we have two additional cases corresponding to when either list is empty. The result in that case is simple: it is just the non-empty list. This is fine, because we are assuming our lists were sorted to begin with.
Let's go back and review some of the similarities between Quicksort and Mergesort, though they look quite different (certainly not as similar as many of the map, filter, or fold functions).
First, we still have base cases. In the language of HtDP, which reframes our input as "problems", these are called "trivially solvable" problems. These are usually relatively simple to take care of. What is more challenging than with structural recursion is ensuring that you have the right set of trivially solvable problems.
For example, while the empty list is a sufficient base case for Quicksort, this is not the case for Mergesort. We observe that Mergesort may produce a list of size one, which would not be able to be divided in half. Thus, a list containing a single element is a necessary, but trivially solvable problem that's distinct from the recursive case.
The recursive cases for both algorithms are interesting to compare. On the surface, they both look the same: simply split your input, the problem, into two smaller problems and recursively solve the problems. Once you have the solutions, put them back together. For Quicksort, these are the two lists we get after pivoting and for Mergesort, these are the two lists we get by splitting the list in half. Each of these problems gets solved recursively. In Quicksort, we combine our solutions by appending the resultant lists together and in Mergesort, we merge the two lists together.
A notable difference between the two is where the work gets done. In other words, if we examine these two algorithms, where do the comparisons (the action that we want to measure) get made? In Quicksort, this happens when we partition our list around the pivot: we compare all elements with the pivot. But in Mergesort, the comparisons get made when we combine our solutions via merging.
Putting this all together, we see that the design of functions that use generative recursion are not quite as clear-cut as with our problems that use structural recursion. The following snippet is an adapted attempt at a template for generative recursion from HtDP:
(define (generative-recursive-fun problem)
(match problem
[trivially-solvable
(determine-solution trivially-solvable)]
[_
(combine-solutions
... problem ...
(generative-recursive-fun
(generate-problem-1 problem))
...
(generative-recursive-fun
(generate-problem-n problem)))]))
Of course, this is fairly vague, but that's kind of the point. Once we stray away from structural recursion, we have an amount of freedom in how we choose to approach our recursion. This can be quite powerful, as we've seen, but it is also a lot more murky in terms of how to approach a solution. This kind of thing is what makes algorithm design challenging.
Now that you've been working on your projects for a bit, it's time to talk a bit about universes again. One of the most difficult parts of writing interactive programs is debugging them, because there are so many moving parts to them. Recall the flow of information in our universes:
And in all of these steps, there are helper functions firing off and passing information back and forth. How does one keep track of all of this information?
A very useful tactic is to simply produce more information. For instance, if we rely solely on the information that we described in the flow of information above, we only see the end result of all of the complex interactions of the code. But what happens with everything in between? Obviously, we don't want the eventual user to see any of the guts, but when we're developing our programs, that is very useful information to have.
One obvious way to do solve this problem is to simply draw the information we want. But this is difficult because there's only one place to do so: in the function responsible for drawing. That is not helpful if one of the secondary helper functions is acting up long before it gets to the drawing!
Here, we will make use of the display function. This function simply displays the value you give it in the interactions pane. This seems immediately useful: we can use display to show information about the world, or really any other information we want, without having to draw it.
However, attempts to use it may cause some issues at first. For instance, suppose we want to use display to show some information depending on the branch of an if expression:
(if boolean-cond
expr1
expr2)
Where does the display expression go? If we try the obvious place, we end up with something like
(if boolean-cond
(display something)
expr1
(display something-else)
expr2)
This does not work out as we want: because display itself is an expression, our if expression interprets it as given. This gives rise to two problems.
First, recall that every expression in Racket is expected to produce a value. But what does display produce? We can figure this out based on its type:
(->* (Any) (Output-Port) Void)
This is quite different from any function types we've seen before, but the important part is the end, which is Void, the output type. We've seen this before when Racket complains that a cond expression doesn't have an else clause. This is because that cond expression may produce no value if all of the other conditions are failed. This is what Void signifies: no value.
What this means is that we can't just go throwing display expressions all over the place, because many expressions have the requirement that exactly one expression is given as an argument, such as in the branches of match expressions.
Secondly, we still have multiple expressions to contend with. What we would like is a way to say that we want to evaluate but ignore certain expressions and package them up so they are treated as a single expression.
Racket is actually quite accomodating here, by providing a syntactic form called begin, which has the following general form:
(begin expr-1 expr-2 ... expr-n)
What this does is it executes each expression in sequence and evaluates to the value of the final expression. This is similar behaviour to what would happen if you just wrote a bunch of expressions in sequence. The difference is that a begin expression is considered a single expression. Practically speaking, this means you can write something like the following:
(begin (display expr-1) (display expr-2) ... expr-n)
What this would do is display a number of expressions and then produce the value specified by the final expression. One can then slide in display expressions at any point with some care. For instance, returning to our if example from earlier, we could write the following:
(if boolean-cond
(begin (display something)
expr1)
(begin (display something-else)
expr2))
Here, each of the begin expressions evaluates each expression in side of it, but ultimately evaluates to the value provided by the final expression in each.