Haskell v. Java In Deducing Prime Numbers

February 16, 2009 - zenoconsultingzenoconsulting


So, I was reading The Haskell Road To Logic, Maths & Programming and in the beginning of the book, they show a simple program to deduce whether a number is prime or not.

I thought I'd implement the parallel in Java. I am still a relative newbie in Haskell, but the point in doing such an exercise is to illustrate how two different languages solve the same problem, and the pros and/or cons of each. It is a small enough example, so I'll start with the Haskell code. I stole this from the book, but re-named a few things to try to make it a bit more readable. Note: wikidot doesn't have a Haskell template for code yet (I guess I should write one) — so syntax coloring is not going to be great.

-- tells you whether you have a prime number or not
isPrime n     
   | n < 1     = error "not a positive integer"
   | n == 1    = False
   | otherwise = leastDivisor n == n
 
leastDivisor n = findLeastDivisor 2 n
 
findLeastDivisor k n 
    | divides k n     = k
    | k^2 > n         = n
    | otherwise       = findLeaseDivisor(k + 1) n
 
divides d n = rem n d == 0

I think the Haskell is pretty readable — even if you don't know Haskell, you can probably grok what it is doing. I re-named some of the functions from the original implementation in the book. I'm probably violating some super-critical Haskell naming rule here, but I just find functions named ld and ldf way too cryptic.

So, if the Haskell code is still too cryptic…take a look at the Java port below. This is pretty much a straight port over from the Haskell implementation. You might argue that there are better ways to do this in Java, but I left it close to the Haskell implementation to make it easier to compare.

package com.example;
 
public class PrimeOrNot {
 
    /**
     * @param args
     */
    public static void main(String[] args) {
        Integer n = 0;
        if(args.length <= 0) {
            usage();
            System.exit(1);
        }
        try {
            n = Integer.parseInt(args[0]);
        } catch(NumberFormatException e) {
            System.err.println(e);
            usage();
            System.exit(1);
        }
        if(n < 1) { System.err.println("not a positive integer"); }
        if(n == 1) { PrintResult(false); }
        PrintResult(leaseDivisor(n));
    }
 
    public static boolean leaseDivisor(int n) {
        return n == findLeastDivisor(2, n);
    }
 
    public static int findLeastDivisor(int k, int n) {
        if(n % k == 0) { return k; }
        else if(Math.pow(k, 2) > n) { return n; }
        else { return findLeastDivisor(k+1, n); }
    }
 
    public static void usage() {
        System.err.println("Usage: "+PrimeOrNot.class+" <integer>");
    }
 
    public static void PrintResult(boolean result) { 
        System.out.println(result); System.exit(0); 
    }
}

So, I guess the first thing to notice is that the Java is a lot more code. You could probably tighten it up, but then again, can Java do this? (Integer.MAX_VALUE)

*Main> isPrime 2147483647
True

Java sez:

Exception in thread "main" java.lang.StackOverflowError
    at java.lang.Math.pow(Math.java:609)
    at com.example.PrimeOrNot.findLeastDivisor(PrimeOrNot.java:32)

Ok, ok — so you can use java.math.BigInteger to get arbitrary precision integers.

You *know* this will fail miserably in Java:

*Main> isPrime 109827359823792837509817235098237509283750923857923857013424230987102398751203987502323293875928375098275098237529835709182735091823750923875943875893475
False

That's pretty cool. So, Haskell uses Tail Code Optimization to make recursion work in constant time. I didn't print the whole stack trace from the Java code, but it included a huge long stack trace list due to the recursion…so, you get the idea.

Ok, you're probably arguing that the use of recursion to solve this problem in Java is naive and bad — and you'd be right. But, I guess the point is recursion often offers simple and elegant solutions to problems, and I like the fact that it doesn't pose a stack overflow pitfall in a language like Haskell.


Backlinks


Add a New Comment
or Sign in as Wikidot user
(will not be published)
- +
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License