implement cons function in Java - type safety question

Question

I am working on a small functional library written in Java, which mimics the a functional style of programming. I am stuck with a undesirable type cast in one of my method definitions and would love some help.

Ok, so we do not have first class functions in Java, so I define them as objects, with one method 'apply()' like so:

public abstract class Function2<R,T1,T2> {
    public abstract R apply(final T1 paramOne, final T2 paramTwo);
}

I then define my cons method as a Function2 object, which I can pass around like I would a function in another language that supports it:

public static <T> Function2<List<T>, T, List<T>> cons(){
    return new Function2<List<T>, T, List<T>>(){
        @Override
        public List<T> apply(T x, List<T> xs) {
            return new NonEmptyList<T>(x, xs);
        }
      };
    }

I have omitted my list structure for brevity; assume it is a functional style list data structure with all the usual head/tail/etc. operations.

I then want to implement a function like 'reverse', which returns a list of items in reverse order. I use foldl1 (fold a non empty list from the left) to achieve this, and pass the cons function as a parameter to foldl1 like so:

public static <T> List<T> foldl( Function2<List<T>, T, List<T>> f,
                                 List<T> acc,
                                 List<T> xs ){
    if(xs.isEmpty()){ return acc; }
    return foldl(f, (f.apply(xs.head(), acc)), xs.tail());
}    

public static <T> List<T> reverse(List<T> xs){
    // how do I avoid this cast??
    return foldl( (Function2) cons(), new EmptyList(), xs); 
} 

But when I pass my 'cons()' object in 'reverse', I need to cast it as a Function2, and I have no idea how to avoid doing this. I have tried all manner of messing around with types...I feel this is simply a lack of experience on my part with the Java type system...anyone?

PS. I am aware of other functional libraries in Java, I just wanted to do my own small one as a learning experience.

EDIT - OK, so I am using a regular 'foldl' now to get back a List, but I still have to perform the cast? The return type of 'cons' align with 'foldl'...

Answer 1

The reason that you can't pass cons as an argument to foldl1 without casting is that the type of cons simply does not match that of foldl1's function argument and your cast is in fact illegal - but, sadly, unchecked, so you don't get an exception right away (you will get one eventually though).

You've defined foldl1 to take a function that takes two arguments of the same type and cons doesn't do that. cons takes a T and a list of Ts. When foldl1 first calls cons, it will call it with the list's first and second elements as arguments. Since neither of those is a list, this will cause a ClassCastException to be thrown.

So cons is simply not a valid argument for foldl1. Not only is there no way to avoid the cast, there's also no way to make the cast actually work.

Another reason that you can't use foldl1 to reverse a list is its return type: foldl1 returns a T where T is the element type of the list you're calling it on. So if you use foldl1 on a list of Ts, the result will be a T. But clearly the result of reversing a list of Ts should be another list of Ts, not a plain T.

If you want to reverse a list using a fold and cons, you'll need to define it in terms of foldl, not foldl1. foldl allows for the result type to be different from the element type of the list and it allows you to use something other than the first element of the list as the starting value of the accumulator (which you need because, as I said, the accumulator needs to be a list).

Answer 2

I went through this stuff earlier, and finally gave up on it, because even the types of simple functions like fold and map were so complicated that it makes programming with them in Java no fun.

But the real pain starts when you need higher kinded types, like that of fmap.

fmap :: Functor f => (a -> b) -> f a -> f b

That is, if you not only want to abstract over the element type (of a list, say), but also about the container (Functor) type, symbolized by f above.

Btw, it is funny: as long as one does not do functional programming, such a need for higher kinded types does never arise, perhaps because one does not even have higher order functions. But when you have them, you realize quite soon that you now want to go a step further. In this regard, it will be interesting to see how Java 8 fares. With the lambda functions, they satisfy a long awaited need, but I am not sure they know they will open Pandoras's box. But higher kinded types would require a substantial rewrite of the Java type system ... or so I think.