Creating own Java Immutable Persistent List - typing issues

Question

I am trying to learn how to create an immutable, persistent list. Right now my implementation is in java, though I'm more interested in the concept and figuring out how to play nicely with static typing.

My first implementation was working. It had final int size, final T head and final PersistentList<T> tail fields. It is just a singly linked list, each node points to another node of the same PersistentList<T> type (via tail field), or null in the case of the end of the list. Herein lies the problem, I don't want null checks everywhere and don't want to use null to represent end of list / empty list. I want to represent an empty list with a new EmptyList object, which would always be the last node in my PersistentList abstract class. This is what clojure does and what Eric Lippert demonstrated (in C#).

My problem is that since this new EmptyList object is of a different type, I'm having issues with specifying the right types in the right places, and the compiler complains.

I created an abstract class IPersistentList, and derived PersistentList and EmptyList from it. The goal is to have the following list structure:

|PersistentList<T>| --> |PersistentList<T>| --> |EmptyList<T>|

Now methods like tail or the static create function need to be able return either a PersistentList<T> or EmptyList<T> instance depending on whether or not it is the last node in the list, but how can I specify the right return type? My guess was to always return the type of the parent abstract class, IPersistentList<T>. But this requires me to always cast the derived classes, which feels horribly dirty and the compiler is still complaining. I also wouldn't want a solution where client code is required to initialize a list of a type and then have to cast. I would like it to be transparent.

Here is a gist of my code. Here is the error:

persistent_list/src/main/java/com/benreinhart/persistentlist/PersistentList.java:15: error: constructor PersistentList in class PersistentList<T#2> cannot be applied to given types;
    PersistentList<T> p = new PersistentList<T>(head, PersistentList.empty(), 1);
                          ^
  required: T#1,IPersistentList<T#1>,int
  found: T#1,IPersistentList<Object>,int
  reason: actual argument IPersistentList<Object> cannot be converted to IPersistentList<T#1> by method invocation conversion
  where T#1,T#2 are type-variables:
    T#1 extends Object declared in method <T#1>create(T#1)
    T#2 extends Object declared in class PersistentList
Note: persistent_list/src/main/java/com/benreinhart/persistentlist/PersistentList.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error

As you can see, the compiler is complaining about my attempt to cast from EmptyList<T> to IPersistentList<T>.

In general, how would I do something like this, given static typing constraints? Is there anyway, and if so, can I accomplish this without casting everywhere? I tried my best to follow the clojure source code for its data structures, but there is so much other stuff in there and I'm pretty new to languages with static typing (and java), so I wasn't able to grasp all of it.

Thanks in advance!

score 1 · Accepted Answer · answered Jul 05 '14 at 22:55

1

The problem is Java cannot infer type argument of empty() method. It gives up and assumes it's Object. EmptyList<Object> cannot be cast to IPersistentList<T>

To fix this, you can pass it explicitly:

PersistentList<T> p = new PersistentList<T>(head, PersistentList.<T>empty(), 1);

extract empty() to temporary local variable:

IPersistentList<T> empty = PersistentList.empty();
PersistentList<T> p = new PersistentList<T>(head, empty, 1);

or use Java 8, which should be able to handle this case.

See here for more details: http://docs.oracle.com/javase/tutorial/java/generics/genTypeInference.html#target_types

answered Jul 05 '14 at 22:55

Piotr Praszmo

17,928
1
57
65

Is Java 8 safe yet? I read they rushed it out and admitted they didn't have time to check it was working properly / secure. – David Knipe Jul 05 '14 at 23:06
Thank you! Your solution fixed the error but now it warns me about unchecked casts. I get this error (from the `empty()` method): persistent_list/src/main/java/com/benreinhart/persistentlist/PersistentList.java:11: warning: [unchecked] unchecked cast return (IPersistentList) EMPTY; ^ required: IPersistentList found: EmptyList where T is a type-variable: T extends Object declared in method empty() 1 warning – Ben Jul 06 '14 at 01:21
Is there any way to get the compiler to think the code is ok (without turning warnings off)? Also, is there any way to accomplish what I am trying to do without having to cast types everywhere? Any tips, ideas? Thanks – Ben Jul 06 '14 at 01:23
I guess for now I'll add "@SuppressWarnings("unchecked")" but I would prefer if there was a way to architect my list without having to constantly cast. It's beginning to look like that might not be possible. – Ben Jul 06 '14 at 01:38
There is no way to tell `(IPersistentList) EMPTY` is safe. Ignore this one case or return new instance instead: `new EmptyList()`. The other cast is not necessary. – Piotr Praszmo Jul 06 '14 at 06:20

Creating own Java Immutable Persistent List - typing issues

1 Answers1