[plt-scheme] How to make the following code more clear?

From: Jos Koot (jos.koot at telefonica.net)
Date: Mon Oct 13 15:38:00 EDT 2008

Your response came in while I was still preparing some comments and it make 
my comments superfluous. However, I am not sure it such a good idea to have 
students write inefficient code like this. I think a warning that designing 
a good sorter is far from trivial, not for a beginner actually. Also a 
warning that the algorithm is far from optimal is in place, I think. Asking 
the student how to avoid traversing the list twice (largest: full traversal, 
remove: partial traversal) is probably asked far too much to a beginning 
student. (This would be asking to invent linear sort)

----- Original Message ----- 
From: "Matthias Felleisen" <matthias at ccs.neu.edu>
To: "SamuelXiao" <foolsmart2005 at gmail.com>
Cc: <plt-scheme at list.cs.brown.edu>
Sent: Monday, October 13, 2008 8:44 PM
Subject: Re: [plt-scheme] How to make the following code more clear?

#lang typed-scheme

(: selectionsort (∀ (α) ((Listof α) (α α -> Boolean) -> (Listof
;; gen. rec.: repeatedly pick/remove the largest value wrt <=, create
lists from it
(define (selectionsort l0 <=)
   (: max (α α -> α))
   (define (max n m) (if (<= n m) m n))

   (: = (α α -> Boolean))
   (define (= n m) (and (<= n m) (<= m n)))

   (: largest ((cons α (Listof α)) -> α))
   ;; pick the largest value from the list
   (define (largest lst)
     (foldr max (car lst) (cdr lst)))

   (: remove ((Listof α) α -> (Listof α)))
   ;; remove the given value from the list
   (define (remove lst val)
       [(= (car lst) val) (cdr lst)]
       [else (cons (car lst) (remove (cdr lst) val))]))

   (: aux ((Listof α) -> (Listof α)))
   (define (aux l)
       [(null? l) '()]
       [else (let ([m (largest l)]) (cons m (aux (remove l m))))]))

   (aux l0))

(equal? (selectionsort '(2 1 4 3) <=) '(4 3 2 1))
(equal? (selectionsort '(2 1 4 3) >=) '(1 2 3 
  For list-related administrative tasks:

Posted on the users mailing list.