I came across a post on (cadr life) the other day about creating a function to find all subsequences of a list with a certain length. The Java version was particularly icky and in his post he shows the equivalent code in a couple of languages. I thought it might be interesting to try it in Groovy so I fired up Intellij Idea and pasted the Java version in.
private static < T > List< List< T >> subn(int n, List< T > li) {
List< List< T > > ret = new ArrayList< List< T >>();
if (n == 0) {
ret.add(new ArrayList< T >());
return ret;
}
if (li.isEmpty()) {
return ret;
}
T x = li.get(0);
List< T> xs = li.subList(1, li.size());
for (List< T> sub : subn(n-1, xs)) {
sub.add(0, x);
ret.add(sub);
}
ret.addAll(subn(n, xs));
return ret;
}
Because Groovy is so close syntactically I was able to paste this in as is and run it without modification.
For my first step I thought I’d remove the static typing. I’m not against statically typed code but for such a small self contained function I’m not sure it adds much.
def subn(n, li) {
def ret = new ArrayList();
if (n == 0) {
ret.add(new ArrayList());
return ret;
}
if (li.isEmpty()) {
return ret;
}
def x = li.get(0);
def xs = li.subList(1, li.size());
for (sub in subn(n-1, xs)) {
sub.add(0, x);
ret.add(sub);
}
ret.addAll(subn(n, xs));
return ret;
}
While this reduces character count it doesn’t change the structure at all. At best it’s very slightly clearer than the original.
Next step was to use array literals:
def subn(n, li) {
def ret = [];
if (n == 0) {
ret.add([]);
return ret;
}
if (li.isEmpty()) {
return ret;
}
def x = li.get(0);
def xs = li.subList(1, li.size());
for (sub in subn(n-1, xs)) {
sub.add(0, x);
ret.add(sub);
}
ret.addAll(subn(n, xs));
return ret;
}
Nice, some more characters trimmed. By simplifying the if statements we can cut back a bit more:
def subn(n, li) {
if (n == 0) return [[]];
if (li.isEmpty()) return [];
def ret = [];
def x = li.get(0);
def xs = li.subList(1, li.size());
for (sub in subn(n-1, xs)) {
sub.add(0, x);
ret.add(sub);
}
ret.addAll(subn(n, xs));
return ret;
}
I’m not really a fan of short variable names so next step is to rename some variables. In addition to this I’ll change the loop slightly to use the each function. The ‘it’ magic variable replaces the ’sub’ variable.
def subn(n, list) {
if (n == 0) return [[]];
if (list.isEmpty()) return [];
def ret = [];
def head = list.get(0);
def remainder = list.subList(1, list.size());
subn(n-1, remainder).each {
it.add(0, head);
ret.add(it);
}
ret.addAll(subn(n, remainder));
return ret;
}
By adding the collections together we can simplify the loop a bit more:
def subn(n, list) {
if (n == 0) return [[]];
if (list.isEmpty()) return [];
def ret = [];
def head = list.get(0);
def remainder = list.subList(1, list.size());
subn(n-1, remainder).each {
ret.add([head] + it);
}
ret.addAll(subn(n, remainder));
return ret;
}
Looking at the code it becomes clear that the ‘ret’ variable is just accumulating the results. We can use the collect method for this purpose instead.
def subn(n, list) {
if (n == 0) return [[]];
if (list.isEmpty()) return [];
def head = list.get(0);
def remainder = list.subList(1, list.size());
def ret = subn(n-1, remainder).collect { [head] + it }
ret.addAll(subn(n, remainder));
return ret;
}
In fact we really don’t need ‘ret’ at all if instead we just add the two collections together:
def subn(n, list) {
if (n == 0) return [[]];
if (list.isEmpty()) return [];
def head = list.get(0);
def remainder = list.subList(1, list.size());
return subn(n-1, remainder).collect { [head] + it } + subn(n, remainder);
}
Finally lets inline the head variable. It’s only used in one place anyway so not really worth keeping it. In addition we’ll use Groovy list indexing to remove the get() call.
def subn(n, list) {
if (n == 0) return [[]];
if (list.isEmpty()) return [];
def remainder = list.subList(1, list.size());
return subn(n-1, remainder).collect { [list[ 0 ]] + it } + subn(n, remainder);
}
Simple. In my opinion this is much clearer than the original and we managed it by making small incremental changes from the Java version.
A lot of the clarity comes from the fact that we have closures. In fact in his next post Ray posted an example using the Java BGGA closure proposal. Here it is reproduced below:
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));
}
While this is a big improvement from the original it is still clouded by a lot of syntax noise IMHO. Either way I’m very keen for closures to make it into the language.
Update: Fixed the formatting. I wish wordpress was a bit nicer with pasted in source code