[racket] a small programming exercise

On Thu, Oct 14, 2010 at 1:10 AM, Shriram Krishnamurthi <sk at cs.brown.edu> wrote:
> Given: A list of numbers.  Assume integers (though it isn't necessary
> for the underlying issue).
>
> Task: To determine how often the first digit is 1, the first digit is
> 2, ..., the first digit is 9, and present as a table.  You may exploit
> DrRacket's pretty-printer, e.g., by using a list of lists:
>
> '((#\1 22.51539138082674)
>  (#\2 16.44678979771328)
>  (#\3 15.567282321899736)
>  (#\4 12.401055408970976)
>  (#\5 9.058927000879507)
>  (#\6 7.651715039577836)
>  (#\7 6.420404573438875)
>  (#\8 5.804749340369393)
>  (#\9 4.133685136323659))

I actually adapted a previous algorithm of mine...

(define (benford ns)
  (let ((ns (if (number? (car ns))
                (map first-digit ns)
                ns))
        (total (length ns)))
    (let benford0 ((ns ns) (digits (map first-digit '(1 2 3 4 5 6 7 8 9))))
      (if (null? digits) '()
        (let* ((d         (first digits))
               (all-d     (filter ns (lambda (n)      (char=? n d))))
               (all-but-d (filter ns (lambda (n) (not (char=? n d))))))
          (pair
           (pair d (* 100.0 (/ (length all-d) total)))
           (benford0 all-but-d (rest digits))))))))

; given these aliases for lisp n00bs
(define pair cons)
(define first car)
(define rest cdr)

; this utility
(define (first-digit n) (string-ref (number->string n) 0))

; and these well-known functions
(define (fold f init ls)
  (if (null? ls) init
    (fold f (f (car ls) init) (cdr ls))))

(define (filter ls f)
  (fold (lambda (i o) (if (f i) (pair i o) o)) '() ls))