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'...

• Ismail Badawi: Well you defined foldl1 as taking Function2<T, T, T>, and cons() returns a Function2<List<T>, T, List<T>>; so it shouldn't type check. It only type checks if you ignore the generics which is what you're doing by casting to the raw type.

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).

• lwm: sorry to demote your answer, your recommendations were correct, but my original problem still persists...
• sepp2k: @LukeMurphy Hard-coding the result type of foldl to List<T> doesn't seem like a good idea. Anyway your problem is that the function given to fold takes a list and a T, while cons takes a T and a list. So you either need to reverse the order in which the function given to fold takes its argument, the order in which cons takes its arguments or define a flip function and pass flip cons as the function argument to foldl.
• sepp2k: @LukeMurphy And it isn't really accurate to say "I have to use a cast" as that would imply the cast works, which I'm pretty sure it won't.
• lwm: I have two versions of foldl, one with the accumulator as a T, and one with the accumulator as a List<T>, so it isn't so much 'hard coded'. The function passed to the foldl takes a T, List<T> , cons takes a T, List<T> and reverse returns a List<T> ? The cast does work...
• sepp2k: @LukeMurphy I just realized it has to be YourClass.<T>cons even if YourClass is the current class. Does that work? If no, please post your whole code, so I can try to compile it myself.

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.

• sepp2k: That's not the proper type for foldl1 (foldl(f, xs.head(), xs.tail()) will not return a list if f doesn't return a list - also it's not the type that foldl1 has in any other language that defines it (like Haskell)). And even it were, that would still not solve the problem since cons doesn't have the type a -> a -> a.
• Ingo: Yes, you're right. I'll edit a bit.