[plt-scheme] Do no evil

I tried to find that quote, but didn't find anything better than what
it says in the "in practice" section of Wikipedia.

(And, of course, we are in a loop here, but this is a new piece of
information related to the loop-- I don't mean for us to cover any old
ground again. Apologies in advance if we head off thataway.)

Robby

On Mon, Mar 8, 2010 at 9:47 AM, Matthias Felleisen <matthias at ccs.neu.edu> wrote:
>
> Knuth wrote this up in the 1960s. Anyone who teaches bubble sort
> in the 20xy is teaching 1970s computer science. But I think I am
> now in some kind of loop with wooks.
>
>
>
>
> On Mar 8, 2010, at 10:44 AM, Robby Findler wrote:
>
>> Continuing my contrarianocity: When I was taught the bubble sort, I
>> wish that my teacher had taken the time to explain bubble sort's place
>> in the pantheon of sorting algorithms (there is essentially no metric
>> under which it better than some other sort, with the possible
>> exception of ease of implementation in Fortran 70).
>>
>> Robby
>>
>> On Mon, Mar 8, 2010 at 9:39 AM, Matthias Felleisen <matthias at ccs.neu.edu>
>> wrote:
>>>
>>> I have taken Veer's understanding to derive a relatively short
>>> form of bubble sort in the plain Scheme language:
>>>
>>> (define (bsort v)
>>>  (define (sweep v i clean?)
>>>   (cond
>>>     [(= i (- n 1)) (if clean? v (sweep v 0 true))]
>>>     [else (if (<= (vector-ref v i) (vector-ref v (+ i 1)))
>>>               (sweep v (+ i 1) clean?)
>>>               (sweep (swap v i) (+ i 1) false))]))
>>>  (define n (vector-length v))
>>>  ;; IN
>>>  (sweep v 0 true))
>>>
>>> ;; swap: factored out as suggested by Noel,
>>> ;; do it with build-vector and weep! bubble
>>> ;; demos how bad FP's performance can be :-)
>>>
>>> But I have done so in ASL just to demonstrate that it is feasible.
>>>
>>> You start with the generative recursion idea of bubbling through
>>> the array until there are no more out of place items left. Then
>>> you're done. Then you 'edit' the program with two observation.
>>> If you were in #lang scheme, you'd come up with the above
>>>
>>> The derivation is appended below. -- Matthias
>>>
>>>
>>>
>>> ;; [Vec Number] -> [Vec Number]
>>> ;; create a sorted version of v
>>> ;; effect: modify v
>>> (define (bsort.v0 v)
>>>  (local (;; Result = (list [Vec Number] Boolean)
>>>
>>>         ;; [Vec Number] -> [Vec Number]
>>>         ;; (effect) create a sorted version of v
>>>         ;; generative recursion: swap-all until nothing to swap anymore
>>>         ;; termination: there are only a finite number of swaps
>>>         (define (generative-driver v)
>>>           (local ((define v+flag (sweep v))
>>>                   (define newv   (first v+flag))
>>>                   (define clean? (second v+flag)))
>>>             (if clean? v (generative-driver v))))
>>>
>>>         ;; [Vec Number] -> Result
>>>         ;; (effect) swap all out of place neighbors throughout vector
>>>         (define (sweep v)
>>>           (local (;; [Vec Number] N Boolean -> Result
>>>                   ;; accumulators: [0,i) is bubbled -- clean? no swaps so
>>> far
>>>                   (define (sweep v i clean?)
>>>                     (cond
>>>                       [(= i (- (vector-length v) 1)) (list v clean?)]
>>>                       [else (if (<= (vector-ref v i) (vector-ref v (+ i
>>> 1)))
>>>                                 (sweep v (+ i 1) clean?)
>>>                                 (sweep (swap v i) (+ i 1) false))])))
>>>             (sweep v 0 true))))
>>>   ;; IN
>>>   (generative-driver v)))
>>>
>>> ;; fold the geneative-driver into the sweep function
>>> ;; observation: the base case packages up the result,
>>> ;; which is immediately unfolded and used for another call
>>>
>>> (define (bsort.v1 v)
>>>  (local (;; [Vec Number] -> [Vec Number]
>>>         ;; (effect) swap all out of place neighbors throughout vector
>>>         (define (sweep v)
>>>           (local (;; [Vec Number] N Boolean -> Result
>>>                   ;; accumulators: [0,i) is bubbled -- clean? no swaps so
>>> far
>>>                   (define (sweep v i clean?)
>>>                     (cond
>>>                       [(= i (- (vector-length v) 1))
>>>                        (if clean? v (sweep v 0 true))]
>>>                       [else (if (<= (vector-ref v i) (vector-ref v (+ i
>>> 1)))
>>>                                 (sweep v (+ i 1) clean?)
>>>                                 (sweep (swap v i) (+ i 1) false))])))
>>>             (sweep v 0 true))))
>>>   ;; IN
>>>   (sweep v)))
>>>
>>> ;; eliminate the indirection from 1-ary sweep through 1-ary sweep
>>> ;; lift the vector-length computation
>>>
>>> (define (bsort v)
>>>  (local (;; [Vec Number] N Boolean -> Result
>>>         ;; accumulators: [0,i) is bubbled -- clean? no swaps so far
>>>         (define (sweep v i clean?)
>>>           (cond
>>>             [(= i (- n 1)) (if clean? v (sweep v 0 true))]
>>>             [else (if (<= (vector-ref v i) (vector-ref v (+ i 1)))
>>>                       (sweep v (+ i 1) clean?)
>>>                       (sweep (swap v i) (+ i 1) false))]))
>>>         ;; where
>>>         (define n (vector-length v)))
>>>   ;; IN
>>>   (sweep v 0 true)))
>>>
>>> ;;
>>>
>>> -----------------------------------------------------------------------------
>>> ;; auxiliaries
>>>
>>> ;; [Vec Number] N -> [Vec Number]
>>> ;; swap items i and i+1 in v
>>> (define (swap v i)
>>>  (local ((define v at i (vector-ref v i)))
>>>   (begin
>>>     (vector-set! v i (vector-ref v (+ i 1)))
>>>     (vector-set! v (+ i 1) v at i)
>>>     v)))
>>>
>>> ;;
>>>
>>> -----------------------------------------------------------------------------
>>> ;; tests
>>>
>>> (define (generate-test) (vector 3 1 9 8 5 6 7 0 4 2))
>>> (define swapped0 (vector 1 3 9 8 5 6 7 0 4 2))
>>> (define swapped2 (vector 3 1 8 9 5 6 7 0 4 2))
>>> (define sorted (vector 0 1 2 3 4 5 6 7 8 9))
>>>
>>> (check-expect (swap (generate-test) 0) swapped0)
>>> (check-expect (swap (generate-test) 2) swapped2)
>>>
>>> (check-expect (bsort (generate-test)) sorted)
>>>
>>> _________________________________________________
>>>  For list-related administrative tasks:
>>>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>>>
>
>