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.


Thomas Quick said...

Well, honestly I cannot say that I am too terribly fond of the '=>' syntax; but what can you ask for in java? At least this will remove some heavy boiler plate.

For the record, I have tried the syntax... I would have preferred something like a colon or a period...

Ray Myers said...

Thomas: The syntax is still open to negotiation, but the arrow (->, ==>, =>, etc...) has a good deal of mathematical and programming language tradition behind it. However, I'll admit that (λ x. x + 2) does reflect Alonzo Church's original notation, as opposed to {int x => x + 2}.

I like the arrow a bit better because it jumps out at you more than dot and colon would. Also, A => B clearly reads as a function "from A to B".

I might also add that in the case of BGGA control abstractions, the user of a library wouldn't have to use the arrow notation at all, they could use normal loop syntax.

Thomas Quick said...

Speaking on the syntax some more; I have figured that the 'best fit' that I can come up with is something like this:

{(List<T> sub) push(first, sub)}

That would give it a bit more similarity to what Java programmers know.

Ray Myers said...

Thomas: A notation for types is also required.
{List<T> sub => push(first, sub)}
has the type:
{List<T> => List<T>}.

What would the type of
{(List<T> sub) push(first, sub)}
look like?
{(List<T>) List<T>} perhaps?

Edson said...

Thomas Quick:
I prefer the BGGA syntax over the "C function pointer"-like syntax that is proposed by a lot of people over and over again.
I am a C/C++ old-timer and find that the "C function pointer" syntax is very awkward and difficult to understand, compared to BGGA's function types.
(The Pizza language has a "C function pointer" syntax but its author - Martin Odersky - abandoned such syntax when created the Scala language. The Scala syntax resembles BGGA's, not Pizza's syntax.

Thomas Quick said...

Actually in the spirit of trying to prove that the C style syntax looked better, I tried it. I have to tell you, for one simple case it looked better; but, for everything else it was pure garbage. I completely support the BGGA style syntax now.

As Ray pointed out, the type notation looks terrible with the C style.

dibblego said...

Here it is in Haskell:

subn n xs = filter ((n ==) . length) (map (take n) (tails xs))

You can indeed abstract away the loop using Functional Java ( with BGGA. I'll write it for you if you like, but maybe you want to try first. Here are some examples of using BGGA with Functional Java

Ray Myers said...

dibblego: Those are substrings, not subsequences. It's a common mix-up.

See also the previous post, "Returning '(()) Considered Difficult", where I gave a Haskell version.

Thanks for the link to Functional Java!