#lang typed/racket
(define-type Inputs (Listof Real))
(define-type Digits (Listof Integer))
(define-type Frequencies (Listof (Pair Integer Real)))

(: freq : Digits -> Frequencies)
(define (freq l)
  (define h (make-vector 10 0))
  (define tot
    (for/fold: : Integer ([tot : Integer 0]) ([e : Integer (in-list l)])
      (vector-set! h e (add1 (vector-ref h e)))
      (add1 tot)))
  (for/list ([(c e) (in-indexed (in-vector h))])
    (cons e (/ c tot))))
(: nums->digits : Inputs -> Digits)
(define nums->digits
  ((inst curry (Real -> Integer) (Listof Real) (Listof Integer)) (inst map Integer Real)
         (compose (λ: ([x : String]) (assert (string->number x) exact-integer?))
                  (compose
                   string
                   (compose
                    (λ: ([x : String]) (string-ref x 0))
                    (compose 
                     real->decimal-string
                     (λ: ([x : Real]) (if (x . < . 0) (- x) x))))))))
(: sk : (Listof Real) -> Frequencies)
(define (sk l)
  (freq (nums->digits l)))
(: sort-em : (Listof (Pair Integer Real)) -> (Listof (Pair Integer Real)))
(define (sort-em l)
  ((inst sort (Pair Integer Real) Real) l >= #:key cdr))

(equal?
 (sort-em
  (sk (list 1/10 0.2 0.3 0.4 5/10 0.6 0.7 0.8 0.9 0.10
            11 12 13 -14 15 16 17 18 19
            21 -22 23 24 25 26 27 28
            31 32 -33 34 35 36 37
            41 42 43 44 45 46
            51 -52 54 54 55
            61 62 -63 64
            71 -72 73
            81 82
            91)))
 (for/list: : (Listof (Pair Integer Real)) ([i : Integer (in-range 10)])
   (cons i
         (/ (- 10 i)
            (+ 10 9 8 7 6 5 4 3 2 1)))))

(define lst (build-list 100000 (λ: ([v : Integer]) (random 11))))
(collect-garbage) (collect-garbage) (collect-garbage)
(time (sort-em (sk lst)))