## 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.

Mike Coffin said...

[Too bad the "pre" tag doesn't work.]

While I prefer this:

int minimumIntegerInBox(Collection> boxes) {
int result = Integer.MAX_VALUE;
for (Box box : boxes) {
if (box.get() instanceof Integer) {
result = Math.min(result, Integer.class.cast(box.get()));
}
}
return result;
}

that would be cheating. So...

-----------------------------------------

package com.foo.box;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

/**
* @author mike
*/
public class Functors {
public interface Function {
Range of(Domain domainItem);
}

public static class Pair {
private A a;
private B b;
public Pair(A a, B b) {this.a = a; this.b = b; }
public A first() { return a; }
public B second() { return b; }
}

public static List map(Iterable items, Function f) {
List result = new ArrayList();
for (D item : items) {
}
return result;
}

public static List filter(Iterable items, Function filter) {
List result = new ArrayList();
for (T item : items) {
if (filter.of(item)) {
}
}
return result;
}

public static R foldLeft(Function, R> f, R initial, Iterable items) {
R result = initial;
for (D item : items) {
result = f.of(new Pair(result, item));
}
return result;
}

public static T best(final Function, Boolean> better, Iterable items) {
return foldLeft(
new Function, T>() {
@Override
public T of(Pair arg) {
T bestSoFar = arg.first();
T candidate = arg.second();
if (bestSoFar == null || better.of(new Pair(bestSoFar, candidate))) {
return candidate;
} else {
return bestSoFar;
}
}
},
null,
items);
}

public static int minimumElement(Iterable items) {
return best(
new Function, Boolean>() {
@Override
public Boolean of(Pair domainItem) {
return domainItem.second() < domainItem.first();
}
},
items);
}

public static List> keepIntegers(Iterable> objects) {
return filter(
objects,
new Function, Boolean>() {
@Override
public Boolean of(Box domainItem) {
return domainItem.get() instanceof Integer;
}
});
}

public static int minimumIntegerInBox(Collection> boxes) {
Iterable> intBoxes = filter(boxes,
new Function, Boolean>() {
@Override
public Boolean of(Box domainItem) {
return domainItem.get() instanceof Integer;
}
});
Iterable ints = map(
intBoxes,
new Function, Integer>() {
@Override
public Integer of(Box domainItem) {
return Integer.class.cast(domainItem.get());
}
});
return minimumElement(ints);
}
}

fawcett said...

A version in the D programming language: