[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>