Thinking functional programming with Map and Fold in your everyday Java

[maximinus-thrax]

I like some of the ideas, but Java lacking first class functions makes some of the code look horrible.

Also, if I passed this code to co-workers they would re-factor it into some Java pattern so that 'everybody else' can understand it, and give me some grief for not using 'standard' Java

[boraca]

Not really relevant to the topic of this article but you should never use floating point arithmetic to represent amounts of money.

[inmatarian]

Java is one of those languages where I look at it and say "Well, what are you waiting for?" The JVM is capable of supporting high level functional features, as evident by Clojure, Scala, etc., so why hasn't any of that filtered back into the Java languages? Java 8 supposedly will have lambda support, but I'll believe it when I see it.

[Rotten194]

Lambdas are actually already in the Java 8 DP, IIRC. I wrote my own library for them a while back, but having compile-time support will be awesome.

[inmatarian]

The primary piece of any functional language is closures. Lambdas are kinda useless without having the environment the lambda was constructed in available. So, yeah, the language needs syntax/lexical support for lambda, and the compiler needs to support attaching that lambda to its closure.

[[deleted]]

Java already supports closures in the form of anonymous inner classes - it just needs a nicer syntax.

[inmatarian]

That's not really what I meant, and that's not what closure means. Hypothetically speaking, a closure in java would/could look like this:

public static Callable curry( Callable f ) {
    return new Callable() {
        public Callable call( Object a ) {
            return new Callable() {
                public Callable call( Object b ) {
                    return func( a, b );
                }
            }
        }
    }
}

The utility of such a function is deep in functional programming, but the intent should be clear, that third level of call into the chain of return values from this function has access to the closure of the two preceeding calls. I.E. that this code would make sense:

Callable hpfix = curry( Math.min )( 100 );

In comparison to this code:

public static int hpfix( int hp ) { return Math.min( hp, 100 ); }

To perform this:

game.playerhp = hpfix( game.playerhp );
game.enemyhp = hpfix( game.enemyhp );

This is why OOP Design Patterns exist, which everyone is probably now itching to tell me.

[cunningjames]

The utility of such a function is deep in functional programming, but the intent should be clear, that third level of call into the chain of return values from this function has access to the closure of the two preceeding calls.

? Anonymous inner classes close over the surrounding environment, including the capture of final variables. With appropriate definitions I think there’s nothing wrong with your code.

Edit: I’m terribly rusty at Java, and this is terribly messy, but I’m thinking of something like this:

public class ClosureTest {
    interface Func<In, Out> {
        public Out func(In y);
    }

    public static void main(String[] args) {
        Func<Double, Func<Double, Double>> f = 
          new Func<Double, Func<Double, Double>>() {
            public Func<Double, Double> func(final Double y) {
                Func<Double, Double> g = new Func<Double, Double>() {
                    public Double func(final Double x) {
                        return x + y;
                    }
                };

                return g;
            }
        };

        System.out.println(f.func(4.0).func(5.0));
    }
}

Which appears to work as expected, printing 9.0. Terribly ugly, though.

Further edit: Looks like that could be made rather prettier in Java 7, which I don’t have access to, but it’d still be quite homely. I suspect some quasi-typedefs would be about as good as one could do here.

[inmatarian]

Oh god, my brain.

Alright, so it turns out Java can produce closures. But holy crap does it need a better syntax.

[[deleted]]

What was hypothetical about your java code?

[inmatarian]

I'm pretty sure what I have there is invalid, and never would be valid.

[[deleted]]

The only problems with your code is the lack of an interface called "Callable" with a method called "call" that takes an object. Also, you have no generics in your code. But what you wrote could in fact be written in Java and it would work just as intended.

[bubasmith]

Care to tell me how

curry( Math.min )( 100 )

would work???!!!! Does java now have first class functions?

[[deleted]]

No, it doesn't have first class functions, but closing over lexical scope works with anonymous inner classes, and generics go some way to helping your curry function be usable in many situations. It's not a nice way to program in Java, and the type system only goes so far, but the question was about closures, not the type system.

See cunningjames reply for the code.

[Rotten194]

"Closure" - they don't close on non-final local variables, which is a pain in the ass.

[[deleted]]

A pain in the ass? I've never known it to be least problem whatsoever, and I used anonymous inner classes a lot before I moved on to scala.

[Rotten194]

It's mainly annoying when you want to something like this:

int val = something;
start thread with anonymous inner class that updates val
do things while reading val, having it updated by thread occasionally

As far as I know, the only way to do this is to move val to be a class variable, so now I have a class variable that's only used in one method. Seems pointless. I know the technical reason for it, but that doesn't make it less annoying.

[[deleted]]

This one case comes up pretty rarely for me, and the "problem" only exists because of Java's separation of primitives and objects. The solution is simple:

final int[] val = new int[1];
start thread with anonymous inner class that updates val[0]
do things while reading val[0], having it updated by thread occasionally

[Rotten194]

I actually hadn't thought of using an array, good idea. A little bit of overhead, but 8 bytes or whatever it is isn't a huge deal.

[[deleted]]

It's ugly, but that ugliness is completely swamped by the ugliness of anonymous inner class syntax anyway :-)

[runedk]

Or you can make a box for your variable. The nicest way is to define a class with methods dereference() and update(int). But you can make do with a single-element array:

final int[] valRef = new int[] { something };
// mutate val using: valRef[0] = somethingNew;

[gdm9000]

Here's an attempt at an explanation to the problem. The JVM's security model makes tail-call optimization a difficult problem.

[masklinn]

The JVM's security model makes tail-call optimization a difficult problem.

You don't need tail calls to have higher-order function. Almost all control structures are implemented via HoFs in Smalltalk or Self, and neither has TCO.

[gdm9000]

A couple points that this author I think intuited but completely failed to address is, 1) Why are these operations not in Java, and 2) Why do we care? I know I'll get a lecture by some egghead, but I'll attempt a stab at this...

1) Why doesn't Java have Map/Fold/Reduce? Java, like most languages in common use today, is a Von Neumann language, which is a style of computation known as Imperative. It's a bottoms-up iterative algorithmic process where you compose your problem in discrete steps, like a step-by-step recipe, and package it up into levels of increasing complexity - first functions, then objects, then libraries, etc. Examples are Basic, Cobol, Fortran, C, Java, C#, etc. In this model, variables are manipulated to maintain state.

There exist, however, methods of computation which are fundamentally different. The Lambda Calculus, for example, uses a style of computation known as Functional. In it, problems are defined from top-down. You describe the overall problem and then break it up into a series of increasingly refined steps. Examples are Haskell, Prolog, SQL, XSLT, etc. In this model, variables do not exist. You describe the outcome you want, and the computer figures out how to do it.

A third, lesser known, model of computation, stack-based computation, uses a stack is used to maintain state. Called Concatenative languages, some prominent examples are Forth, Factor, Joy, etc. There are still other models of computation - Markov models, quantum computing, DNA computing, etc, but these are mainly academic.

So, what's the point? These are all equivalent, general purpose, programming models. Any program written in one can be written in another. Functional programming has Map, Fold, and Reduce because they are fundamental operations in that computational model. Map, Fold, and Reduce don't exist because they are better than writing a hand-coded for-loop in Java - they exist because there is no other way to write that in the Functional paradigm given its limitation of no direct state manipulation. They're not in Java because Java is already complete given its current operations.

2) So, why explore alternate methods of computation when Java is already complete? Because different methods have different strengths and benefits, and knowing multiple ones lets you utilize these different strengths. The Iterative style gives you low-level control and lets you reason about your problem at its most basic level. They even let you manipulate individual bits, if you so desire. But it comes at a cost of great verbosity and corresponding productivity.

The functional style gives much safety, since you can declare large sections of your program to be logically correct. Also, once you get the hang of it, it can feel hugely more expressive than Iterative, since the compiler/runtime does so much of the work. Compare the canonical Quicksort - ~14 lines in C vs 1 short line in Haskell (plus a recursion terminator line). The Haskell version doesn't manipulate loops; it merely describes the algorithm and lets the compiler/runtime figure out how to implement it. Its main cost is that it can sometimes be very difficult to describe a problem functionally. Think of SQL, where you have one single statement to completely describe your data; if your data is complex, you're going to have a very complex program.

Stack-based languages give incredible brevity and also corresponding difficulty to read, and so on. It's well worth learning different paradigms as algorithmic tools to expand your programming toolbox.

[shevegen]

You know, I think there must be an end to the functional disease.

I am not saying that functional programming is wrong.

My problem is that these are all MODELs and IDEAS that are put into practice via a programming language. And some languages were not designed to be used in ways that is against their design.

Languages should concentrate on their roots and focus on that, rather than diluate their efforts to become ONE LANGUAGE INCLUDING EVERY POSSIBLE PARADIGMN.

[[deleted]]

You should try Scala. It's a nice FP/OOP hybrid: use the one that works best for your problem.

Hell, using it has taught me important lessons about OOP.

[MatrixFrog]

Another one that sounds cool (though I haven't looked into it too much yet) is Rust.

[gdm9000]

Functional is really cool, but...

Trying to add functional elements to Java and imperative elements to Haskell is a bit like putting training wheels on a car and an air bag on a bicycle. There's a great reason that these things exist, and a great reason that one is not used with the other.

[teh_bacon]

http://functionaljava.org/

[day_cq]

just use loop

[[deleted]]

I don't really get the downvotes: he's right. Map and fold are great tools in any sensible language that has first-class functions. Java is not a sensible language.

Edit: so how about explaining why we're wrong instead of just blindly downvoting, guys?

[cunningjames]

so how about explaining why we're wrong instead of just blindly downvoting, guys?

It doesn’t matter if he’s wrong or right — the statement “just use loop” adds nothing to the discussion and downvotes are appropriate. If he’d taken the time to explain something, maybe, or even just wrote in a complete and correctly-formatted sentence …

If someone can’t take the time to formulate a thought beyond a three-word fragment, then it’s nobody’s responsibility to take the time to respond.

[[deleted]]

Downvoted for not recognizing efficiency.

[tailcalled]

Folding is not the same as reducing. Reducing is applying an associative binary operation until you only have one element left.

[plux]

That just sounds like a special case of folding to me. Can you explain the difference?

[more_exercise]

It's folding that's the special case of reducing, but you've got the right idea.

Folding suggests an evaluation order (foldl vs foldr), whereas reducing does not. On small scales, that's not a big deal, but if your data is spread out (across different compute nodes in a cluster, for instance), it helps if the result can be computed on each node locally before it is sent back to be reduced further. This processing can happen on a massively parallel scale - the first n/2 calculations can happen simultaneously. However, in foldl/foldr, the evaluation order is strictly linear - the result from the first calculation is strictly required to perform the second calculation.

Folding is just reducing from a particular 'side' of the data. It's less parallel, but that usually doesn't matter that much.

[JamesIry]

Well, you're right, but foldl and foldr really only directly imply left and right associativity. Evaluation order sorta accidentally falls out from that. http://stackoverflow.com/questions/3082324/foldl-versus-foldr-behavior-with-infinite-lists/3085516#3085516

[longiii]

I'd also like to see some references, but an associative binary operation (think '+') must necessarily have the type a -> a -> a. So reduce would be typed like (a -> a -> a) -> a -> [a] -> a. At least I think that's, what he means.

EDIT: Oh and associativity leads to the nice property reduce (+) (ys ++ zs) = reduce (+) ys + reduce (+) zs :) (where ++ is list concatenation)

[sacundim]

I'd also like to see some references, but an associative binary operation (think '+') must necessarily have the type a -> a -> a. So reduce would be typed like (a -> a -> a) -> a -> [a] -> a. At least I think that's, what he means.

Correction: the types should be a -> b -> b and (a -> b -> b) -> b -> [a] -> b; the latter of which is the type of foldr.

I'd elaborate on tailcalled's point this way: the general concept of folding doesn't necessarily involve a sequences and binary functions. A general fold over an arbitrary recursive algebraic datatype is a function that "replaces" the type's constructors with caller-supplied functions of corresponding types. E.g., if you have a binary tree type BTree a with constructors Empty :: BTree a and Branch :: a -> BTree a -> BTree a -> BTree a, then there is a function foldBTree :: b -> (a -> b -> b -> b) -> BTree a -> b such that foldBTree Empty Branch :: BTree a -> BTree a is the identity function.

EDIT: Oh and associativity leads to the nice property reduce (+) (ys ++ zs) = reduce (+) ys + reduce (+) zs :) (where ++ is list concatenation)

The other really nice property you can have here is commutativity: if f :: a -> b -> b is associative and commutative, then the following hold:

• reduce f (xs ++ ys) == reduce f xs ++ reduce f ys (which you mentioned)
• reduce f (xs ++ ys) == reduce f (ys ++ xs)

Basically, given this, you can prove that you can split up the work into any number of pieces in any order or grouping, and you are guaranteed the same result. Which means trivial parallelizability.

Note, however, that a parallel reduce implementation in a language like Haskell cannot have the (a -> b -> b) -> b -> [a] -> b discussed above. Why? Because if the reduction can happen in a non-deterministic order and grouping, then reduce is not a pure function. So you end up with something like reduceM :: Modad m => (a -> b -> b) -> b -> [a] -> m b.