Tuesday, June 8, 2010

An illustrative problem.

I'm working on a fairly simple problem and I think it illustrates something interesting. Here is the problem statement:

A `box' is an object that has a name and can hold another object of a particular type (that is, there are boxes for integers, boxes for strings, boxes for floats, etc.) You are given an unordered collection of various boxes and must find the smallest integer among the subset of boxes that contain integers.

To make it a tiny bit more challenging, we won't just write an ad-hoc loop. We'll use map, filter, and fold-left. Since fold-left is a bit scary, I'll write that part:
(define (best better? list)
  (fold-left (lambda (best-so-far candidate)
               (if (or (null? best-so-far)
                       (better? candidate best-so-far))
                   candidate
                 best-so-far))
             '()
             list))

(define (minimum-element list)
  (best < list))
So assuming that *box-list* is a variable containing our list of boxes, Exercise 1 is to write a program in Scheme or Lisp using map, filter, and minimum-element that finds the smallest integer (fixnum) in the boxes.

Too easy? Let's make it a bit trickier: Code up the identical solution in Java.

Assume that Box is a generic (that is, parameterized) type, so Box<Integer> would contain an Integer and Box<String> contains a String, etc. The variable BoxList would be declared as Collection<Box<?>>, so we want a method with this signature: int minimumIntegerInBox (Collection<Box<?>> boxes)

I don't think it can be done without getting at least one Unchecked conversion warning, but a cleverly placed @SuppressWarnings("unchecked") will permit you to downcast a Box<?> to a specific type, and then everything else should type check.
Post a Comment