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.
[Too bad the "pre" tag doesn't work.]
ReplyDeleteWhile 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) {
result.add(f.of(item));
}
return result;
}
public static List filter(Iterable items, Function filter) {
List result = new ArrayList();
for (T item : items) {
if (filter.of(item)) {
result.add(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);
}
}
A version in the D programming language:
ReplyDeletehttp://codepad.org/5gc6tuxb
(In the spirit of disclosure, there's a bug in the current release of the D compiler which prevents this from working; it should be fixed in the next minor release.)
The exclamation marks indicate template (compile-time macro) invocations. The templates are instantiated with the "a < b..." strings as parameters; these are DSL expressions that will compile to efficient, type-safe code.
Lispers might appreciate that both the variant type and the higher-order functions are defined in library code, not in core D.
Just a quick follow-up to my earlier comment: the latest release of the D compiler and its standard library (version 2.0.4.8) does indeed fix the bug I mentioned; the snippet I posted executes as promised.
ReplyDelete