implement cons function in Java – type safety 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’…

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

12

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.

2

Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa Dịch vụ tổ chức sự kiện 5 sao Thông tin về chúng tôi Dịch vụ sinh nhật bé trai Dịch vụ sinh nhật bé gái Sự kiện trọn gói Các tiết mục giải trí Dịch vụ bổ trợ Tiệc cưới sang trọng Dịch vụ khai trương Tư vấn tổ chức sự kiện Hình ảnh sự kiện Cập nhật tin tức Liên hệ ngay Thuê chú hề chuyên nghiệp Tiệc tất niên cho công ty Trang trí tiệc cuối năm Tiệc tất niên độc đáo Sinh nhật bé Hải Đăng Sinh nhật đáng yêu bé Khánh Vân Sinh nhật sang trọng Bích Ngân Tiệc sinh nhật bé Thanh Trang Dịch vụ ông già Noel Xiếc thú vui nhộn Biểu diễn xiếc quay đĩa Dịch vụ tổ chức tiệc uy tín Khám phá dịch vụ của chúng tôi Tiệc sinh nhật cho bé trai Trang trí tiệc cho bé gái Gói sự kiện chuyên nghiệp Chương trình giải trí hấp dẫn Dịch vụ hỗ trợ sự kiện Trang trí tiệc cưới đẹp Khởi đầu thành công với khai trương Chuyên gia tư vấn sự kiện Xem ảnh các sự kiện đẹp Tin mới về sự kiện Kết nối với đội ngũ chuyên gia Chú hề vui nhộn cho tiệc sinh nhật Ý tưởng tiệc cuối năm Tất niên độc đáo Trang trí tiệc hiện đại Tổ chức sinh nhật cho Hải Đăng Sinh nhật độc quyền Khánh Vân Phong cách tiệc Bích Ngân Trang trí tiệc bé Thanh Trang Thuê dịch vụ ông già Noel chuyên nghiệp Xem xiếc khỉ đặc sắc Xiếc quay đĩa thú vị
Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa
Thiết kế website Thiết kế website Thiết kế website Cách kháng tài khoản quảng cáo Mua bán Fanpage Facebook Dịch vụ SEO Tổ chức sinh nhật