Tuesday, July 12, 2011

Concatenative Thinking

I've written about the conciseness of Factor before. Yesterday, I noticed a link to a functional programming tutorial called "Functional Thinking" that was posted two months ago.

The tutorial develops a program for classifying numbers based on the sum of its factors into perfect, abundant, or deficient numbers. The program goes through three improvements, ending up at this "best" solution in Java (using the Functional Java library):

public class FNumberClassifier {

    public boolean isFactor(int number, int potential_factor) {
        return number % potential_factor == 0;
    }

    public List<Integer> factors(final int number) {
        return range(1, number+1).filter(new F<Integer, Boolean>() {
            public Boolean f(final Integer i) {
                return number % i == 0;
            }
        });
    }

    public int sum(List<Integer> factors) {
        return factors.foldLeft(fj.function.Integers.add, 0);
    }

    public boolean isPerfect(int number) {
        return sum(factors(number)) - number == number;
    }

    public boolean isAbundant(int number) {
        return sum(factors(number)) - number > number;
    }

    public boolean isDeficient(int number) {
        return sum(factors(number)) - number < number;
    }
}
While the proffered solution is much (much) better than the original "imperative" solution, I thought I would show what it could look like in Factor:
: factor? ( m n -- ? )
    mod zero? ;

: factors ( n -- seq )
    dup [1,b] [ factor? ] with filter ;

: perfect? ( n -- ? )
    [ factors sum ] [ - ] [ = ] tri ;

: abundant? ( n -- ? )
    [ factors sum ] [ - ] [ > ] tri ;

: deficient? ( n -- ? )
    [ factors sum ] [ - ] [ < ] tri ;
What do you think?

5 comments:

yac said...

Factor solution sure is concise and elegant, especially in contrast with the bloat and ugliness of Java.

As of "functional thinking in Java", that's what Scala is for ;)

diego.a said...

A person would only need to know a few things about the Factor language to understand what you are trying to do here. The Java version requires more experience.

I guess this means you took Java to school, gave it a D grade, and called its parents.

Dave Newton said...

You only need to know a few things about Java, too.

The isFactor method doesn't need to exist as the example stands, its functionality is duplicated in the factors closure.

Factor assumes semantic knowledge of stack values, whereas it's explicitly stated (in long form) in this example. (I'm talking about variable names, not type information, in this case.)

With those changes the Java example stands at a mere 2x Factor's character count, compared to nearly 3x w/ the original.

Still ugly, still bloated, but a more realistic comparison.

Dave Newton said...

You only need to know a few things about Java, too.

The isFactor method doesn't need to exist as the example stands, its functionality is duplicated in the factors closure.

Factor assumes semantic knowledge of stack values, whereas it's explicitly stated (in long form) in this example. (I'm talking about variable names, not type information, in this case.)

With those changes the Java example stands at a mere 2x Factor's character count, compared to nearly 3x w/ the original.

Still ugly, still bloated, but a more realistic comparison.

mrjbq7 said...

@Dave: You are right that it's partly due to the static nature of Java.

In Part 2, the author shows a version in Clojure which is much closer to Factor (albeit with a lot more parens).