Transcript Lesson 8.1 Sometimes Structural Recursion Isn't Enough

Sometimes Structural Recursion
Isn't Enough
CS 5010 Program Design Paradigms
“Bootcamp”
Lesson 8.1
© Mitchell Wand, 2012-2013
This work is licensed under a Creative Commons Attribution-NonCommercial 3.0 Unported License.
1
Module Introduction
• Sometimes problems don't fit neatly into the
pattern of recursion on the sub-pieces of the
data.
• In this module, we'll see some examples of
problems like this, and introduce a new design
strategy, general recursion, to handle this.
• General recursion and invariants together
provide a powerful combination.
2
General Recursion is more powerful
than structural decomposition
• Functions written using structural decomposition
are guaranteed to halt with an answer, but
general recursion allows you to write functions
that don't always halt.
• So every time we write a function using general
recursion, we need to provide a termination
argument that explains why the function really
does halt
– or else warn the user that it may not halt.
– easiest way to make a termination argument is by
supplying a halting measure.
3
Data
Representations
Design
Strategies
Basics
Function
Composition
Mixed Data
Structural
Decomposition
Recursive Data
Module 08
Generalization
Over Constants
Over Expressions
Generalization
Functional Data*
Objects &
Classes
Stateful Objects
Over Contexts
General
Recursion
Over Data
Representations*
Communication
Over Method
via State
Implementations
* we’ll touch on these topics briefly
4
Learning Objectives
• At the end of this lesson, the student should
be able to
– identify two common algorithms that do not fit
into the pattern of structural decomposition +
accumulator
– explain why they can't be made to fit the pattern
5
An example: decode
(define-struct diffexp (exp1 exp2))
;; A DiffExp is either
;; -- a Number
;; -- (make-diffexp DiffExp DiffExp)
Here is the data definition for diffexps.
These are a simple representation of
difference expressions, much like the
arithmetic expressions we considered
in some of the earlier problem sets.
6
Examples of diffexps
(make-diffexp 3
(make-diffexp 2
(make-diffexp
(make-diffexp
(make-diffexp
5)
(make-diffexp 3 5))
2 4)
3 5))
Writing out diff-exps is tedious at best.
7
Not very human-friendly...
• How about using more Scheme-like notation,
eg:
(- 3 5)
(- 2 (- 3 5))
(- (- 2 4) (- 3 5))
8
Task: convert from human-friendly
notation to diffexps.
• Info analysis:
– what's the input?
– answer: S-expressions containing numbers and
symbols
9
Data Definitions
;; An Atom is one of
;; -- a Number
;; -- a Symbol
Here is a formal data
definition for the
inputs to our
function.
;; An SexpOfAtom is either
;; -- an Atom
;; -- a ListOfSexpOfAtom
;; A ListOfSexpOfAtom is either
;; -- empty
;; -- (cons SexpOfAtom ListOfSexpOfAtom)
10
Templates
And the templates
to go with it.
(define (sexp-fn sexp)
(cond
[(atom? sexp) (... sexp)]
[else (... (los-fn sexp))]))
(define (los-fn los)
(cond
[(empty? los) ...]
[else (... (sexp-fn (first los))
(los-fn (rest los)))]))
11
Contract and Examples
decode : SexpOfAtom -> DiffExp
(- 3 5) => (make-diffexp 3 5)
(- 2 (- 3 5)) => (make-diffexp
2
(make-diffexp 3 5))
(- (- 2 4) (- 3 5))
=> (make-diffexp
(make-diffexp 2 4)
(make-diffexp 3 5))
12
Umm, but not every SexpOfAtom
corresponds to a diffexp
(- 3)
(+ 3 5)
(- (+ 3 5) 5)
((1))
((- 2 3) (- 1 0))
(- 3 5 7)
does
does
does
does
does
does
not
not
not
not
not
not
correspond
correspond
correspond
correspond
correspond
correspond
to
to
to
to
to
to
any
any
any
any
any
any
diffexp
diffexp
diffexp
diffexp
diffexp
diffexp
But here are some other inputs that
are legal according to our contract.
None of these is the human-friendly
representation of any diff-exp.
13
A Better Contract
;; A Maybe<X> is one of
;; -- false
;; -- X
;; (define (maybe-x-fn mx)
;;
(cond
;;
[(false? mx) ...]
;;
[else (... mx)]))
To account for this, we
change our contract to
produce a MaybeDiffExp
instead of a DiffExp.
If the SexpOfAtom
doesn't correspond to any
DiffExp, we'll have our
decode function return
false.
decode
: SexpOfAtom -> MaybeDiffExp
14
Function Definition (1)
;; decode : SexpOfAtom -> MaybeDiffExp
;; Algorithm: if the sexp looks like a diffexp at the top level,
;; recur, otherwise return false. If either recursion fails, return
;; false. If both recursions succeed, return the diffexp.
(define (decode sexp)
(cond
[(number? sexp) sexp]
[(looks-like-diffexp? sexp)
(local
((define operand1 (decode (second sexp)))
(define operand2 (decode (third sexp))))
(if (and (succeeded? operand1)
(succeeded? operand2))
(make-diffexp operand1 operand2)
false))]
[else false]))
Now we can write the function definition.
15
Function Definition (2)
;; looks-like-diffexp? : SexpOfAtom -> Boolean
;; WHERE: sexp is not a number.
;; RETURNS: true iff the top level of the sexp looks like
;;
a diffexp.
;; At the top level, a representation of a
;; diffexp must be either a number or a list of
;; exactly 3 elements, beginning with the symbol ;; STRATEGY: function composition
(define (looks-like-diffexp? sexp)
(and
In this function definition, we add
(list? sexp)
an invariant (the WHERE clause)
to record the assumption that our
;; at this point we know that
input is not merely an
;; sexp is a list
SexpOfAtom, but is rather an
(= (length sexp) 3)
SexpOfAtom that is not a number.
(equal? (first sexp) '-)))
We know this assumption is true,
because looks-like-diffexp? is only
called after number? fails.
16
Function Definition (3)
;; succeeded? : Maybe<X> -> Boolean
;; RETURNS: Is the argument an X?
;; strategy: Struct Decomp on Maybe<X>
(define (succeeded? mx)
(cond
[(false? mx) false]
[else true]))
And we finish with the help
function succeeded? .
17
But wait: what's the strategy?
;; decode : SexpOfAtom -> MaybeDiffExp
;; Algorithm: if the sexp looks like a diffexp at the top level,
;; recur, otherwise return false. If either recursion fails, return
;; false. If both recursions succeed, return the diffexp.
(define (decode sexp)
(cond
[(number? sexp) sexp]
[(looks-like-diffexp? sexp)
(local
((define operand1 (decode (second sexp)))
(define operand2 (decode (third sexp))))
(if (and (succeeded? operand1)
(succeeded? operand2))
(make-diffexp operand1 operand2)
But what strategy is this? It
false))]
doesn’t fit the template for
[else false]))
SexpOfAtom. It’s not even
close.
18
Something new happened here
• We recurred on the subpieces, but
– we didn't use the structural predicates
– we didn't recur on all of the subpieces
• This is not structural decomposition
19
Another example: merge-sort
• Let's turn to a different example: merge sort,
which you should know from your
undergraduate data structures or algorithms
course.
• Divide the list in half, sort each half, and then
merge two sorted lists.
20
merge
;; merge : SortedList SortedList -> SortedList
;; merges its two arguments
;; strategy: structural decomposition on both arguments
;; (see book)
To define merge-sort, we
(define (merge lst1 lst2)
start with merge, which
(cond
merges two sorted lists of
numbers. This is one of the
[(empty? lst1) lst2]
few places where we really
[(empty? lst2) lst1]
need structural
[else
decomposition on two lists
(if (< (first lst1) (first lst2))
at once. The textbook
(cons (first lst1)
contains more information
(merge (rest lst1) lst2)) on this topic.
(cons (first lst2)
(merge lst1 (rest lst2))))]))
If the lists are of length n, this function
takes time proportional to n. We say
that the time is O(n).
21
merge-sort
;; merge-sort : ListOfNumber -> SortedList
(define (merge-sort lon)
(cond
[(empty? lon) lon]
[(empty? (rest lon)) lon]
[else
(local
((define evens (even-elements lon))
(define odds (odd-elements lon)))
(merge
(merge-sort evens)
(merge-sort odds)))]))
Now we can write merge-sort.
merge-sort takes its input and
divides it into two
approximately equal-sized
pieces.
Depending on the data
structures we use, this can be
done in different ways. We
are using lists, so the easiest
way is to take every other
element of the list, so the list
(10 20 30 40 50) would be split
into (10 30 50) and (20 40) .
We sort each of the pieces,
and then merge the sorted
22
results.
Running time for merge sort
• Splitting the list in this way takes time proportional to
the length n of the list. The call to merge likewise takes
time proportional to n. We say this time is O(n).
• If T(n) is the time to sort a list of length n, then T(n) is
equal to the time 2*T(n/2) that it takes to sort the two
sublists, plus the time O(n) of splitting the list and
merging the two results:
• So the overall time is
T(n) = 2*T(n/2) + O(n)
• When you take algorithms, you will learn that all this
implies that T(n) = O(n log n). This is better than an
insertion sort, which takes O(n^2).
23
Something new happened here
• Merge-sort did something very different: it
recurs on two things, neither of which is (rest
lon) .
• We recurred on
– (even-elements lon)
– (odd-elements lon)
• Neither of these is a sublist of lst
– We didn't follow the data definition!
24
Summary
• You should now be able to
– identify two common algorithms that do not fit
into the pattern of structural decomposition +
accumulator
– explain why they can't be made to fit the pattern
25
Next Steps
• If you have questions about this lesson, ask
them on the Discussion Board
• Do the Guided Practice 8.1
• Go on to the next lesson
26