Thursday, April 10, 2008

Subsequences With BGGA Closures

Just a quick followup on Returning '(()) Considered Difficult. I just rewrote the "subsequences of length n" exercise yet again (surprise, surprise), this time using the Java BGGA prototype by Neal Gafter et al. I really like being able to abstract away the accumulation loop.
import static com.cadrlife.ListUtils.*;
private static <T> List<List<T>> subn(int n, List<T> list) {
if (n == 0) {
return Collections.<List<T>>singletonList(new ArrayList<T>());
if (list.isEmpty()) {
return new ArrayList<List<T>>();
T first = list.get(0);
List<T> rest = list.subList(1, list.size());
return addAll(collect(subn(n-1, rest), {List<T> sub => push(first, sub)}),
subn(n, rest));

A word on syntax: Some people have come down on the {=>} closure syntax but I wonder if they have actually used it. This was my first time using BGGA; everything compiled and worked on the first try. I can't say the same about trying to simulate closures with anonymous Transformer classes using the Apache Commons CollectionUtils version of collect.

Just in case you don't have com.cadrlife.ListUtils in your classpath, here are the obvious definitions of collect, addAll, and push.
package com.cadrlife.ListUtils;
public static <A,B> List<B> collect(List<A> list, {A => B} function) {
List<B> result = new ArrayList<B>();
for (A element : list) {
return result;
public static <T> List<T> push(T el, List<T> list) {
list.add(0, el);
return list;

public static <T> List<T> addAll(List<T> a, List<T> b) {
return a;

FunctionalJ: Steve points out that the last bit could be done this way, using the Java library FunctionalJ.
DynReflect reflect = new JdkDynReflect();
Function1 pushFirstElem = reflect.staticFunction(
AnnotatedSequencer.class, "push").f2().bind(first(list));
return addAll(map(pushFirstElem, subn(n - 1, tail(list))),
subn(n, tail(list)));
Be forewarned that using reflection to simulate first-order functions in this way will sacrifice compile-time verification.