1 min read

Histograms in APL/Scheme

Eric gave a talk today about the Connection Machines and CM Lisp. One of the examples was of a way to compute the histogram of a set of numbers:

(β+ X ⍺1)

The basic idea here is that given a Xector X (e.g. -- [5 5 2 5 3 2]), you can compute a Xector of the counts of each using the above expression.

I began to think that this looks a lot of like an APL function/operator combination, so I went to my APLX scrapbook to find something for a histogram. I found one, but I was not quite happy with it. It works well enough, but it does not handle arrays that don't have a one in them. Instead, with a little twist, I managed to make it work for any given range:

⍝ Another Possibility

Of course, why stop there when we can use a few more characters and get the actual visual representation of things all laid out for us:

' ⎕'[⎕IO+(⌽⍳⌈/A)∘.≤A←+/((⌊/X)+⍳1+(⌈/X)-⌊/X)∘.=X]

This actually does a bit more than the CM Lisp expression above does. The output of this for an array X where X=5 5 2 5 3 2 would be something more like this:

⎕  ⎕
⎕⎕ ⎕

And of course, none of this would be complete without an example in Scheme of doing the same thing.

(define (histogram x)
  (let* ([sm (apply min x)] 
         [rng (1+ (- (apply max x) sm))] 
         [v (make-vector rng 0)]
         [inc (lambda (n) (vector-set! v n (1+ (vector-ref v n))))])
    (for-each inc x)
    (map list 
      (map (lambda (x) (+ x sm)) (iota rng))
      (vector->list v))))

Without a doubt, the β operator in CM Lisp is a very cool thing. It's almost like a combination of APL's reduce and indexing operators combined into one. We simulate this sort of behavior using a matrix in the APL version, and in the Scheme version, I manually do the tracking with the vector.

Actually, I think both the APL and Scheme versions are pleasantly concise. If I did not care about keeping the actual indexes in the Scheme version, then it would be even more concise.