[racket] about HTDP quick-sort dead loop?

On 12/9/11 8:37 AM, mahaitao wrote:
> Hi ,
>
> When I read HTDP-Generative Recursion, I test quick-sort in Fig 68 and
> all is right.
> But when I try to replace "<" with "<=" in function "smaller-items" and
> add new cond
> "[(empty? (rest alon)) alon]" (do as the book Section 26 said), the new
> quick-sort doesn't work and
> run in a dead loop.

There are two unrelated changes going on that you shouldn't tangle together:

(1) replacing `<' with `<=' in `smaller-items'
(2) adding a cond-clause to `quick-sort' for the 1-element list case

Part (1): The code for `smaller-items' in section 26 is illustrating 
what can go wrong when the problem generation step of a generative 
recursion design goes wrong, so you are seeing the intended loop 
behavior.  The problem is the alternative `smaller-items' that uses `<=' 
instead of `<' generates problems that are no easier to solve than the 
original problem in some cases.

Read the termination argument given for `quick-sort'.  Is it a valid 
argument when `smaller-items' uses `<='?

Part (2): The additional cond clause is being added to make explicit a 
fact about `quick-sort' that was implicit in the original version, 
namely that (quick-sort (list N)) = (list N), for all numbers N.  This 
additional case does not change the function, but it does make more 
knowledge about the function explicit in its definition.

David