java - How is my implementation of an immutable stack? - Code Review Stack Exchange

java - How is my implementation of an immutable stack? - Code Review Stack Exchange

Writing an elegant immutable stack is difficult in Java, mainly due to the lack of multiple return values. But your code does look quite fine.

I am comparing your API with Scala's immutable stack. One interesting bit is that there the signature of push translates to:

public <T2 super T> ImStack<T2> push(T2 e)

which looks uncomfortable but makes a lot of sense too: Adding elements to a stack can widen the type but never narrow it down. Keeping the current type is a special case of this.

Your isEmpty method is unfortunately flawed. Assume I have created a stack of one element, like:

Object myObject = null;  ImStack<Object> stack = new ImStack<Object>(myObject, null);

Now stack.peek() is correctly null. On an empty stack, this should have created an exception, not returned a null.

One solution to solve this problem is to have isEmpty() always return false. We also create a private subclass¹ of ImStack called ImEmptyStack, where isEmpty() returns true, and peek() throws an exception. In your constructor, you create a new empty stack as tail when that argument would be null:

ImStack(T head, ImStack<? extends T> tail) {    this.head = head;    this.tail = tail != null ? tail : new ImEmptyStack<T>();  }

_{1: Actually, subclassing here leads to problems. The two classes should both be subtypes of a common interface. So basically, the Composite Pattern.}

By overriding the size() in the ImEmptyStack, you can simplify that as well:

class ImStack<T> {    public int size() {      return 1 + tail.size();    }  }    class ImEmptyStack<T> extends ImStack<T> {    public int size() {      return 0;    }  }

Back to your isEmpty() method, code like this should never happen:

if ( head == null && tail == null)      return true;  else return false;

because it is equivalent to return(head == null && tail == null). Every time you write code like return foo() ? true : false, you know you can simplify that.

I'd like to sketch your reverse() method in a more functional manner, using an accumulator argument:

public ... reverse() {    return this.reverse(new ImEmptyStack<T>());  }    private ... reverse(ImStack<...> acc) {    return tail.reverse(acc.push(head));  }    // Empty stack:    private ... reverse(... acc) {    return acc;  }

This is as efficient as your solution, because your size call also traverses the whole stack recursively. The advantage of my solution is the simplicity. Of course, it is trivial to rewrite this to an iterative solution, because the above sketch is tail recursive:

reverse() {    ImStack<T> accumulator = new ImEmptyStack();    ImStack<T> current     = this;    while(!( current instanceof ImEmptyStack<T> )) {      accumulator = accumulator.push(current.peek());      current     = current.pop();    }    return accumulator;  }

Note that .pop() can never return null in my adaption of your code (an empty stack should throw an exception).

---

Something minor that I noticed is your inconsistent spacing around the argument lists of your methods:

ImStack ( T head, ImStack<T> tail)  // left outer and inner space  pop()  // no space  push( T e) // left inner space

This is no problem in itself, but it would be better to settle for one style.

Read full article from java - How is my implementation of an immutable stack? - Code Review Stack Exchange