Weird code example from "Realm of Racket"

Question

I am currently reading the book "Realm Of Racket", which I really like so far. However, in chapter 4 1/2, on page 74, there is one code example that I just don't get. Maybe my mind refuses to figure it out because I am on vacation, however, I simply don't get what it does.

(define (winners lst pred)
  (cond
    [(empty? lst) (list pred)]
    [else
      (define fst (first lst))
      (if (score> (record-score pred) (record-score fst))
        (list pred)
        (cons pred (winners (rest lst) fst)))]))

They don't really explain it in the book. They give some hints, though:

• "The purpose of the function is to pick the first-place finishers from a list of game records."
• "We have a struct definition of the following shape: (struct record (name score))"
• "lst is a list of such records, and pred is one such record. Indeed, the original list is (cons pred lst), and it is sorted according to score."
• "You understand that winners is a list-eating function and goes through one record at a time. When there is at least one other record, it picks the first one, names it fst, and compares the scores of fst and its predecessors. Depending on the outcome, all winning records have been picked off or winners has to continue the search for equal-scoring players."

I suppose that score> is a typo. Besides that I fully understand the code - in terms of syntax and semantics. I just don't get the practical use of that. What is this and why would somebody want that?

Answer 1

Unfortunately the code you are displaying is just to show you how local definitions work. In the same example you also see (define sorted-lst (sort lst ...)) which won't work at all.

Here is the whole example code from page 75, which has all the parts of page 74 in it:

(define (winning-players lst)
  (define sorted-lst (sort lst ...)) ;; local variable 
  (define (winners lst pred)         ;; locally defined procedure
    (cond
      [(empty? lst) (list pred)]
      [else
       (define fst (first lst))
       (if (score> (record-score pred) (record-score fst))           
           (list pred)           
           (cons pred (winners (rest lst) fst)))]))
  ;; START HERE:
  ;; uses both local variable and the locally defined procedure
  (winners (rest sorted-lst) (first sorted-lst))) 

What they tried to show in the following code is that outside winning-players you cannot access sorted-list nor use the procedure winners since it's hidden in winning-players' scope.

Eg. if you try to use (winners ...) in racket interactions windows you get:

winners: undefined; cannot reference undefined identifier

If you understood that you can continue to the fun in chapter 5 :)

Bundled with racket you have all the code from the code from the book under racket/collects/realm. There are 2 defintions of procedures called winners. The first in chapter 10 and the second in chapter 12.

As for the answer to what the code does. There is errors in the code so we need to fix that. My guess is that score> compares the scores of two records. I'm guessing it's supposed to be like this:

(struct record (name score) #:transparent)
(define (winning-players lst)
  (define (score> e1 e2)  ; defines a new local procedure
    (> (record-score e1)  ; that compares two records 
       (record-score e2)))

  ;; define sorted-list to be lst sorted by score in decreasing order
  (define sorted-lst (sort lst score>))  
  ;; procedure winners reduces the list to the elements 
  ;; that have same score as pred
  (define (winners lst pred)            
    (cond
      [(empty? lst) (list pred)]
      [else
       (define fst (first lst))
       (if (score> pred fst)           ;; changed to work with records
           (list pred)           
           (cons pred (winners (rest lst) fst)))]))
  ;; START HERE:
  ;; uses both local variable and the locally defined procedure
  (winners (rest sorted-lst) (first sorted-lst))) 

(define scores (list (record "John" 10) 
                     (record "Ben" 5) 
                     (record "Mary" 10) 
                     (record "Owen" 2)))  

(winning-players scores) 
; ==> (list (record "John" 10) (record "Mary" 10))

It returns a list of all the ones with the highest score.

Answer 2

(winners (cdr lst) (car lst))

produces the non-decreasing streak of records in lst. pred stands for "predecessor" (in the list). I assume score> is a procedure which compares scores of records (i.e. record-score seems to produce score of a record, and score> compares these scores).

IOW for a given list lst its prefix is produced such that the scores of record entries in it are in non-decreasing order.

The description states that the list is sorted before winners is applied. This only makes sense if it is sorted in decreasing order of record's score. Than that non-decreasing prefix of a decreasing list will actually contain records all with equal score - the maximal one. The "winners".

The precondition of the list being sorted in non-increasing order should have been stated much more clearly and prominently there.