[plt-scheme] HtDP 26.1.2

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/f977e0ca/attachment.html>