I knew as soon as I wrote about implementing a simple prime number algorithm using Groovy that someone would find a more elegant way of solving the problem. In this post, I want to highlight some of the responses I received.
In my previous post, The Closure Of No Return, I discussed implementing an isPrime method that worked for relatively small integers. The algorithm is to try to divide the given number by all integers from two up to the square root of the number, rounded up.
My initial attempt, and the actual motivation for the blog post, was to demonstrate that if you use a return keyword inside a closure, you only return from the closure. So my initial implementation didn’t work:
[sourcecode language=”groovy”]
// THIS DOESN’T WORK
boolean isPrime1(int x) {
if (x == 2) return true
int limit = Math.sqrt(x) + 1
(2..limit).each { n ->
// nice try, but a return in a closure
// returns only from the closure
if (x % n == 0) return false
}
return true
}
[/sourcecode]
The each method takes a closure as an argument, which is like calling a completely separate method. The return statement inside the closure returns from that method, but not from the each loop itself.
In order to return the proper value, I introduced a local variable, called result, which I assigned inside the closure and then returned:
[sourcecode language=”groovy”]
boolean isPrime2(int x) {
if (x == 2) return true
boolean result = true
int limit = Math.sqrt(x) + 1
(2..limit).each { n ->
if (x % n == 0) {
result = false
// can’t break out of the loop
}
}
return result
}
[/sourcecode]
Since I couldn’t use the break keyword inside the loop, this implementation was forced to check all the integers up to limit. I therefore switched at that point to Groovy’s for-in loop, which does allow the break:
[sourcecode language=”groovy”]
boolean isPrime3(int x) {
if (x == 2) return true
boolean result = true
int limit = Math.sqrt(x) + 1
for (n in 2..limit) {
if (x % n == 0) {
result = false
break
}
}
return result
}
[/sourcecode]
That was my final implementation in the blog post. I posted that one the web and waited for the corrections to roll in.
One commenter, Eric Johansson, pointed out that once I switched to the for-in loop, I could go back to using return again and eliminate the local variable result. Of course that’s true, and I missed it because of the steps I went through to write the code. I wonder how often such hysteresis loops occur in practice.
Another person commenting on the post, identified at Tim but without an email address or a link, suggested using the any method:
[sourcecode language=”groovy”]
boolean isPrime3(int x) {
if (x == 2) return true
int limit = Math.sqrt(x) + 1
!(2..limit).any { n ->
x % n == 0
}
}
[/sourcecode]
The hope here is that the any method would stop at the first number that satisfied the closure. I wasn’t sure that was true, so I looked at the source code for Groovy, which can be found on GitHub. The any method is shown in the Groovy JDK as being part of the java.lang.Object class. One way methods are added to the Java standard library is through the metaprogramming methods in
org.codehaus.groovy.runtime.DefaultGroovyMethods. I looked in that class and found the any implementation, which adds the any method to the java.lang.Object class:
[sourcecode language=”groovy”]
// from DefaultGroovyMethods
public static boolean any(Object self, Closure closure) {
BooleanClosureWrapper bcw = new BooleanClosureWrapper(closure);
for (Iterator iter = InvokerHelper.asIterator(self); iter.hasNext();) {
if (bcw.call(iter.next())) return true;
}
return false;
}
[/sourcecode]
If I’m interpreting this correctly, the iterator walks through each element one by one and returns true the first time an element satisfies the closure. In other words, yes, this approach would work and leave the loop at the proper time.
Soren (sorry, I don’t know how to put the line through the “o”) Berg Glasius (http://twitter.com/sbglasius) suggested using the every method instead, which would also probably do the job.
Both great developer Jochen Theodorou and the indefatigable Tim Yates immediately identified the obvious alternative that I missed. Here’s Tim’s solution (which is a slight variation on Jochen’s):
[sourcecode language=”groovy”]
boolean isPrime5(int x) {
int limit = Math.sqrt(x) + 1
x == 2 || !(2..limit).find { n -> x % n == 0 }
}
[/sourcecode]
I remembered the findAll method, which I used in my tests, but I forgot all about the find method, which returns the first element that satisfies the closure. That’s pretty ironic, too, because (in Grails especially) I normally accidentally use find when I meant findAll.
(As an aside, as soon as I saw Tim’s name, I assumed his solution was going to be both elegant and have the take method in there somewhere. I was half right.)
The only problem I have with these solutions is that while they work, they invalidate the real reason for my blog post, which was to emphasize that a return inside a closure returns only from the closure. Still, that last one feels like a really good way to solve the actual problem, so I’m going to use that in the future.
The best part is that everyone who suggested an alternative was quite friendly about it. I may have felt a bit foolish for missing these alternatives, but that’s my own pressure on myself. One of the best features about the Groovy community is how helpful and easy to work with everyone is, which I really like. Hopefully by posting those solutions here, I’m paying some of that forward.
(Thanks to everyone who responded, whether I quoted them here or not. I really appreciate the feedback.)
Leave a Reply