How to implement List, Set, and Map in null free design?

Question

Its great when you can return a null/empty object in most cases to avoid nulls, but what about Collection like objects?

In Java, Map returns null if key in get(key) is not found in the map.

The best way I can think of to avoid nulls in this situation is to return an Entry<T> object, which is either the EmptyEntry<T>, or contains the value T.

Sure we avoid the null, but now you can have a class cast exception if you don't check if its an EmptyEntry<T>.

Is there a better way to avoid nulls in Map's get(K)?

And for argument sake, let's say this language don't even have null, so don't say just use nulls.

Answer 1

Throw an exception. Examples of this are .NET's KeyNotFoundException, Java's ArrayIndexOutOfBoundsException, and Python's KeyError.

As we all know exceptions are for exceptional situations, so users should be expected to check that a key exists before looking it up.

Good

if collection.contains(key):
    return collection.get(key);

Bad

try:
    return collection.get(key);
catch KeyError:
    pass # Don't care.

Answer 2

You could throw an "Element not present excepton", but exceptions are expensive, and should be reserved for "Exceptional situations". A value not being present in a map is hardly the case, so it might be a speed bump, but as usual, it depends on the context you are in.

Either way, as an advice, you should consider using the contains(key) method. There's always the posiblity that key has been mapped to the null value, so get(key) would return null, even if present in your map !!!.

Edit:

After watching get()´s source code, I came up with something ( for the record: completely untested and current time here is 01:08 AM, and I have a terrible cold !!)

  314       public V get(Object key) {
  315           if (key == null)
  316               return getForNullKey();
  317           int hash = hash(key.hashCode());
  318           for (Entry<K,V> e = table[indexFor(hash, table.length)];
  319                e != null;
  320                e = e.next) {
  321               Object k;
  322               if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
  323                   return e.value;
  324           }
                //This could be instanced by reflection (bad idea?)
  325           return new MappeableElementImpl();
   }

I you could force V to implement some interface such as MappeableElement or something like that which had a method boolean isUnmappedValue(), then the get() method could return an instance of that interface.

So it would end up in something like:

Element e = map.get(notpresentkey);

if (e.isUnmappedValue()){sysout (notpresentkey  +" is not present");}

Answer 3

Two possible solutions:

1. Provide a contains(key) function. Throw an exception if get(key) is called for a non-existent key. The downside is: calling get() after contains() duplicates operations; not efficient.

2. Functional languages use Maybe in similar situations. This article explains how to implement Maybe in Java.

Answer 4

Return an instance of a generic Optional<T> type.

Answer 5

I suppose you could return an object that has a boolean for Found and an Item that has either the found item or throws an exception. Another way is to use a TryGet technique.

Answer 6

There are three possibilities as I see it.

• Return a null or a Null Object.
• Throw and catch an exception.
• Or avoid the issue by calling containsKey before you call get.

If you're worried about the Null Object being the wrong type, then you could design your map to accept a NullObjectFactory, that creates a special Null Object of the correct type for what you're dealing with (as in the Null Object pattern). That way you could get from a Map without having to check if it contains the key, without having to check if it returns a null, and without having to catch any exceptions.

Answer 7

I understand that you are looking for an alternative to null, but the alternatives all seem to result in some Exception case, which is much more expensive (generating stacktraces,etc.) than testing for null.

So to keep in the game, return an InvalidValueException when trying to insert an invalid (ie null) value or return a NoValuePresentException on a bad get(). (all the while wishing there was a simple null test that you could perform)

Answer 8

Is your question caused by some unusual requirement or scenario for the data structure you're designing, or are you just theoreticizing? If it's the latter, you might want to consider the fact that null is conceptually indistinguishable from any other reference value (e.g. ref to some final obj denoting null), and exceptions are expensive. Unless you have a specific concern or goal making you ask this question, you're really wasting (y)our time. Cheers!

Answer 9

Conceptually it is a big problem. One of useful scenarios is to create adapter which delegates all calls into underlying map object. For this adapter there will be required parameter which specify null object. E.g:

class MapAdapter<K,V> implements Map<K,V> {
    private Map<K,V> inner = new HashMap<K,V>();
    private final V nullObject;

    private MapAdapter(V nullObject) {
        this.nullObject = nullObject;
    }

    public static <K,V> Map<K,V> adapt(Map<K,V> mapToAdapt, V nullObject) {
        MapAdapter<K,V> adapter = new MapAdapter<K,V>(nullObject);
        adapter.inner.addAll(mapToAdapt);
        return adapter;
    }


    //Here comes implementation of methods delegating to inner.


   public V get(K key) {
       if (inner.containsKey(key)) {
           return inner.get(key);
       }
       return nullObject;
   }
}

A lot of work, but it allows generic NullSafe implementation.

Answer 10

Cf. @Doug McClean above -- this sounds like what Scala calls Option and Haskell calls Maybe. It's a lot like what you described, with the Entry and EmptyEntry -- Scala uses Some for the valid Entrys and None for the EmptyEntry.

Daniel Spiewak has a good intro to Option, including a basic Java implementation. (Instead of his instanceof None check, though, I would probably have an isNone() method, and maybe just have one None instance -- since Java generics are erased at run time, and it never actually contains anything, you can cast it, or have a "factory" method that casts it, to whatever None<T> you need.)

Answer 11

It looks like Maybe and Option is the way to go.

But pattern matching is also required to make it simpler for the user of this class. This way the user does not need to use instanceof and cast with the risk of a real time class cast exception.