[plt-scheme] HtDP 26.1.2

Why should merge-neighbors call merge-all-neighbors?

That design decision was driven partly by reason, partly by necessity.
 Since the first condition of "merge-neighbors" disposes of (lon) and (first
lolon) by merging them, something needs to be done with (rest lolon).  The
lists contained in (rest lolon) are un-merged, and so it seemed reasonable
to send them back to "merge-all-neighbors" to do the job.  Also, since
"merge-all-neighbors" is the only function which accepts a single (listof
(listof numbers)) argument, it seemed necessary to do so. Bad reason, I
admit, but I couldn't think of anything else.

How many generative recursions do you think a program such as merge-sort
should use? More than one is extremely rare.

I have no idea.  I think the problem is that I don't really understand the
basics of generative recursion.  I need to back up.  Even if the solution
"works," I'm not really interested in it if it's not functioning as an
instance of generative recursion.

"The function merge-all-neighbors merges the items on the given list in a
pair-wise fashion: the first and second, the third and the fourth, etc. The
function merge uses merge-all-neighbors until there is only one list left on
the list."

This is helpful, although I believe you could reasonably expect a student to
intuit it from the book examples.  My initial problem was failing to
distinguish "merging" from "appending."  Once I got that straight, I
understood the goal of the "merge-all-neighbors."  I was hoping my
(check-expect....) examples made that clear.

Let me start with the design recipe for generative recursion from HtDP:

(define (generative-recursive-fun problem)
 (cond
   [(trivially-solvable? problem)
    (determine-solution problem)]
   [else
    (combine-solutions
      ... problem ...
      (generative-recursive-fun (generate-problem-1 problem))

      (generative-recursive-fun (generate-problem-n problem)))]))

Start the design with a trivially solvable problem, which in this case (I
believe) is a (listof (listof numbers)) consisting of only a single (listof
numbers)).

(define (merge-all-neighbors a-lolon)
    (cond
        [(empty? (rest a-lolon)) a-lolon]
        [else...
      (combine-solutions
      ... problem ...
      (generative-recursive-fun (generate-problem-1 problem))

      (generative-recursive-fun (generate-problem-n problem)))]))

The next thing to do is to merge pairs, or the first and second lists in
a-lolon.  The only way I can imagine doing that is by merging (first
a-lolon) with (first (rest a-lolon)).

But that has to be wrong.  Suppose the value of a-lolon is (list (list 1)
(list 2)).  If (first a-lolon) merges with (first (rest a-lolon)), then it
forces the "merge-all-neighbors" to recur on (rest (rest a-lolon)).  That
would return empty, which is not a trivially-solvable problem.

The only way around that is for "merge-all-neighbors" to test for (empty?
a-lolon).  The final result would look like this --

(define (merge-all-neighbors a-lolon)
  (cond
    [(empty? a-lolon) empty]
    [(empty? (rest a-lolon)) a-lolon]
    [else
     (cons (merge (first a-lolon) (first (rest a-lolon)))
           (merge-all-neighbors (rest (rest a-lolon))))]))

I considered this design possibility earlier because it seems to work, but
I'd be shocked if it was right.  It violates too many of conditions of the
design recipe by 1) including a possible value for a-lolon that doesn't
exist in it's data definition, and, 2) not using merge-all-neighbors to
recur on (merge (first a-lolon) (first (rest a-lolon))).

What is my problem?  Where is my blind spot?  I'm not very encouraged by the
fact I've come up with two poorly designed solutions to what seems like a
fairly straight-forward problem.  It makes me feel as though my design
compass is broken.

I'm trying very hard to understand how basic algorithms are designed, but
it's not coming to me.  All help and suggestions are greatly appreciated!

Thanks for your patience.

Dave Yrueta

On Sun, Mar 22, 2009 at 12:01 PM, Matthias Felleisen <matthias at ccs.neu.edu>
wrote:
>
> Why should merge-neighbors call merge-all-neighbors?
> How many generative recursions do you think a program such as merge-sort
should use? More than one is extremely rare.
> Having said that, I guess the description of the algorithm doesn't bring
out the process as much as I hoped for. How would this work for you:
> "The function merge-all-neighbors merges the items on the given list in a
pair-wise fashion: the first and second, the third and the fourth, etc. The
function merge uses merge-all-neighbors until there is only one list left on
the list."
>
> On Mar 22, 2009, at 2:19 PM, David Yrueta wrote:
>
> Thank you all for your responses.
> Borrowing the "merge" function already developed and tested in Chapter 17,
I came up with the version of "merge-all-neighbors" copied below.
> It seems to work, although the second clause of "merge-all-neighbors"
troubles me --
>
>  [else (merge-neighbors (first lolon) (rest lolon))]))
>
> -- because it doesn't recur on (rest lolon) with "merge-all-neighbors."
 It makes me think I'm deviating from the design recipe.  On my first pass,
when I thought I was strictly adhering to the structural recursion template,
this is what I came up with --
> (define (merge-all-neighbors lolon)
>   (cond
>     [(empty? (rest lolon)) lolon]
>     [else (merge-neighbors (first lolon) (merge-all-neighbors
(rest lolon)))]))
> When I did that, I was surprised to discover that "merge-all-neighbors"
behaved almost identically to "merge-sort," which "merge-all-neighbors" is
supposed to act as an auxiliary function to:
> In this case, (merge-all-neighbors (list (list 5) (list 4) (list 3) (list
2)) returns (list (list 2 3 4 5)), which was not my intention, but seemed
productive.
> Anyway, thoughts and comments are greatly appreciated.  Bottom line: is my
version of "merge-all-neighbors" below correct, lucky, or wrong (meaning
I've missed test cases)?
> ;Data Definitions
> ;A list-of-numbers (lon) is either
> ;1 empty, or
> ;2 (cons n lon) where n is a number
> ;A list-of-list-of-numbers (lolon) is either
> ;1. (cons lon empty), or
> ;2. (cons lon lolon) where lon is a list-of-numbers
> ;merge-all-neighbors : (listof (listof numbers)) -> (listof (listof
numbers))
> ;consumes a lolon, returns a merged lolon; to merge two lists means to
append them in ascending order
> ;(check-expect (merge-all-neighbors (list empty)) (list empty))
> ;(check-expect (merge-all-neighbors (list (list 2 5))) (list (list 2 5)))
> ;(check-expect (merge-all-neighbors (list (list 2 5) (list 3 9))) (list
(list 2 3 5 9)))
> ;(check-expect (merge-all-neighbors (list (list 2 5) (list 3 9) (list 4
8))) (list (list 2 3 5 9) (list 4 8)))
> ;(check-expect (merge-all-neighbors (list (list 2) (list 5) (list 9) (list
3))) (list (list 2 5) (list 3 9)))
> (define (merge-all-neighbors lolon)
>   (cond
>     [(empty? (rest lolon)) lolon]
>     [else (merge-neighbors (first lolon) (rest lolon))]))
> ;merge-neighbors : (listof numbers) (listof (listof numbers)) -> (listof
(listof numbers))
> ;consumes a lon and a lolon; returns a lolon with the lon merged with the
first lon from the lolon
> ;(check-expect (merge-neighbors (list 1 3) (list (list 2 4))) (list (list
1 2 3 4)))
> ;(check-expect (merge-neighbors (list 2 4) (list (list 1 3))) (list (list
1 2 3 4)))
> ;(check-expect (merge-neighbors (list 1 3) (list (list 2 4)(list 5 7)))
(list(list 1 2 3 4)(list 5 7)))
> ;(check-expect (merge-neighbors (list 2 5) (list (list 1 3 4) (list 6 7)))
(list (list 1 2 3 4 5) (list 6 7)))
> (define (merge-neighbors lon lolon)
>   (cond
>     [(empty? (rest lolon))
>      (list (merge lon (first lolon)))]
>     [else (cons (merge lon (first lolon))
>                 (merge-all-neighbors (rest lolon)))]))
> ;merge : (listof numbers) (listof numbers) -> (listof numbers)
> ;consumes two lon sorted in ascending order, returns a single lon sorted
in ascending order
> ;(check-expect (merge empty (list 1 3)) (list 1 3))
> ;(check-expect (merge (list 1 3) empty) (list 1 3))
> ;(check-expect (merge (list 1 3) (list 2 4 5)) (list 1 2 3 4 5))
> ;(check-expect (merge (list 2 4 5) (list 1 3)) (list 1 2 3 4 5))
> (define(merge alon1 alon2)
>   (cond
>     [(and(empty? alon1)(empty? alon2))empty]
>     [(empty? alon1)(cons(first alon2)(merge alon1 (rest alon2)))]
>     [(empty? alon2)(cons (first alon1)(merge (rest alon1) alon2))]
>     [else
>      (cond
>        [(<=(first alon1)(first alon2))(cons (first alon1)(merge(rest
alon1) alon2))]
>        [else(cons(first alon2)(merge alon1 (rest alon2)))])]))
> Thanks!
> Dave Yrueta
>
>
>
>
>
>
> On Sun, Mar 22, 2009 at 7:34 AM, Marco Morazan <morazanm at gmail.com> wrote:
>>
>> On Sat, Mar 21, 2009 at 7:50 PM, David Yrueta <dyrueta at gmail.com> wrote:
>> > How can this accomplished --
>> > (check-expect (merge-all-neighbors (list (list 9) (list 1))) (list
(list 1
>> > 9)))?
>> >
>> > -- without some sorting going on within "merge-all-neighbors"?
>>
>> Your function, merge-all-neighbors, needs to process two pieces of
>> data of arbitrary size. You need to decide how both pieces of data
>> have to be processed. Do you only need to traverse one list at a time?
>> Do you need to traverse both lists at the same time?
>>
>> There is also an assumption that you seem to not have picked up. In
>> addition to being (listof number), what other property should you
>> assume each of the inputs has? Is (merge-all-neighbors (list 2 1)
>> (list 8 9)) a "legal" application of merge-all-neighbors to two lists
>> of numbers?
>>
>> After figuring out the above, I suggest you think about how
>> (merge-all-neighbors (list 2 8 9) (list 1 3 7 10)) can yield (list1 2
>> 3 7 8 9 10). This should tell you how the inputs need to be processed.
>>
>>
>> --
>>
>> Cheers,
>>
>> Marco
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20090322/35edbcc4/attachment.html>