Sort a list of structures in Racket by more than one key

Question

I have list-of-cars, a list of structures of type car with fields "maker", "model" and "year". With regular Racket sort function I can sort by one key (for example "maker"). But how can I sort by both maker and model and come up with a list equal to output of sort-by-maker-and-model in the example?

This is not a school assignment, I have tried to make a clear example with data less boring than actual data I need to work on. Expensive cars seems not too boring to me.

Enjoy my crafty example! Have a nice day!

#lang racket/base

(define-struct car (maker model year) #:transparent)

(define list-of-cars (list (car "Ferrari" "250 Europa GT" "1954")
                           (car "Bugatti" "Type 2" "1900")
                           (car "Lamborghini" "Flying Star II" "1966")
                           (car "Bugatti" "Type 10" "1908")
                           (car "Ferrari" "166 Inter" "1949")
                           (car "Bugatti" "Type 5" "1903")
                           (car "Maserati" "A6 1500" "1946")
                           (car "Ferrari" "340 America" "1951")
                           (car "Maserati" "5000 GT" "1959")
                           (car "Maserati" "Quattroporte" "1963")
                           (car "Lamborghini" "Egoista" "2013")))

(define (sort-by-maker lst)
  (sort lst
        string<?
        #:key car-maker))

(sort-by-maker list-of-cars)
; =>
(list
 (car "Bugatti" "Type 2" "1900")
 (car "Bugatti" "Type 10" "1908")
 (car "Bugatti" "Type 5" "1903")
 (car "Ferrari" "250 Europa GT" "1954")
 (car "Ferrari" "166 Inter" "1949")
 (car "Ferrari" "340 America" "1951")
 (car "Lamborghini" "Flying Star II" "1966")
 (car "Lamborghini" "Egoista" "2013")
 (car "Maserati" "A6 1500" "1946")
 (car "Maserati" "5000 GT" "1959")
 (car "Maserati" "Quattroporte" "1963"))

(define (sort-by-maker-and-model lst)
  ; ???
  #f)

(sort-by-maker-and-model list-of-cars)
; =>
(list
 (car "Bugatti" "Type 2" "1900")
 (car "Bugatti" "Type 5" "1903")
 (car "Bugatti" "Type 10" "1908")
 (car "Ferrari" "166 Inter" "1949")
 (car "Ferrari" "250 Europa GT" "1954")
 (car "Ferrari" "340 America" "1951")
 (car "Lamborghini" "Egoista" "2013")
 (car "Lamborghini" "Flying Star II" "1966")
 (car "Maserati" "5000 GT" "1959")
 (car "Maserati" "A6 1500" "1946")
 (car "Maserati" "Quattroporte" "1963"))

Answer 1

Racket's sort is stable so another alternative is to call sort twice. Of course this requires two passes but that may be fine depending on your purposes. (Note that string<? doesn't produce the result you want in the model column, since "Type 10" is lexicographically first.)

(define (sort-by-maker-and-model lst)
  (sort
   (sort lst string<? #:key car-model)
   string<? #:key car-maker))

(require rackunit)
(check-equal?
 (sort-by-maker-and-model list-of-cars)
 (list
  (car "Bugatti" "Type 10" "1908")
  (car "Bugatti" "Type 2" "1900")
  (car "Bugatti" "Type 5" "1903")
  (car "Ferrari" "166 Inter" "1949")
  (car "Ferrari" "250 Europa GT" "1954")
  (car "Ferrari" "340 America" "1951")
  (car "Lamborghini" "Egoista" "2013")
  (car "Lamborghini" "Flying Star II" "1966")
  (car "Maserati" "5000 GT" "1959")
  (car "Maserati" "A6 1500" "1946")
  (car "Maserati" "Quattroporte" "1963")))

UPDATE: add some timing data

(define (sort-by-maker-and-model lst)
  (sort
   (sort lst string<? #:key car-model)
   string<? #:key car-maker))
(define (sort-by-maker-and-model2 lst)
  (sort lst
        (lambda (e1 e2)
          (or (string<? (car-maker e1) (car-maker e2))
              (and (string=? (car-maker e1) (car-maker e2))
                   (string<? (car-model e1) (car-model e2)))))))
(define (sort-by-maker-and-model3 lst)
  (sort lst
        string<?
        #:key (lambda (e) (string-append (car-maker e) " " (car-model e)))))

(define (random-string)
  (define len (+ 4 (random 6)))
  (apply string (map integer->char (build-list len (λ _ (+ (random 26) 65))))))
(define (random-car . xs)
  (car (random-string) (random-string) (number->string (+ (random 9000) 1000))))
(let ([cars (build-list 1000000 random-car)])
  (collect-garbage)
  (collect-garbage)
  (collect-garbage)
  (void (time (sort-by-maker-and-model cars)))
  (collect-garbage)
  (collect-garbage)
  (collect-garbage)
  (void (time (sort-by-maker-and-model2 cars)))
  (collect-garbage)
  (collect-garbage)
  (collect-garbage)
  (void (time (sort-by-maker-and-model3 cars))))

The custom less-than is fastest, then double sorting, then string appending the keys, which is what I would have guessed:

$ racket sort-cars.rkt
cpu time: 5008 real time: 5015 gc time: 76
cpu time: 1960 real time: 1967 gc time: 0
cpu time: 6633 real time: 6643 gc time: 1588

Answer 2

You need to create your own less-than? comparison function:

(define (sort-by-maker-and-model lst)
  (sort lst
        (lambda (e1 e2)
          (or (string<? (car-maker e1) (car-maker e2))
              (and (string=? (car-maker e1) (car-maker e2))
                   (string<? (car-model e1) (car-model e2)))))))

Alternatively, you could just create a key procedure that concatenates the 2 fields:

(define (sort-by-maker-and-model lst)
  (sort lst
        string<?
        #:key (lambda (e) (string-append (car-maker e) " " (car-model e)))))

This should work here but the former is a more general approach. Any way:

> (sort-by-maker-and-model list-of-cars)
(list
 (car "Bugatti" "Type 10" "1908")
 (car "Bugatti" "Type 2" "1900")
 (car "Bugatti" "Type 5" "1903")
 (car "Ferrari" "166 Inter" "1949")
 (car "Ferrari" "250 Europa GT" "1954")
 (car "Ferrari" "340 America" "1951")
 (car "Lamborghini" "Egoista" "2013")
 (car "Lamborghini" "Flying Star II" "1966")
 (car "Maserati" "5000 GT" "1959")
 (car "Maserati" "A6 1500" "1946")
 (car "Maserati" "Quattroporte" "1963"))