How stateless can you go?

I've attended an Oslo Coding Dojo named "How stateless can you go?" lead by Thomas K. Nilsson. The goal was to write a toString() method for a tree structure printing nodes with proper indentation w.r.t. their depth and then to make it as stateless as possible without any other regard (such as performance or cleanliness of the code).

It was very interesting to compare the original, stateful version and the resulting stateless one and to see the solution in various languages (Haskell, Clojure, Groovy, C#, Java, Scala) - it looked actually pretty similar in all.

What I've learned is that stateless (i.e. functional-style) code looks much cleaner for you get rid of lot of noise such as local variables and loops. In practice it is important to use a language with an efficient implementation of recursion (especially tail-recursion) and with data structures that lead themselves easily to recursive processing, i.e. make it easy and efficient to process the first element of a collection and do that recursively for the rest without modifying the collection (and providing utility methods like each). It is of course best to have languages that support map/reduce.

You can check the slides and various solutions at GitHub and see our primitive and stateless implementations below. (We did it in a nearly TDD-manner, but I won't include the test here as it isn't essential.)

Update: There are more solutions linked to from the meetup's comments - search for "github" - and there is also a link to an article series for deeper discussion of challenges in writing pure and stateless code.

Solution by Jakub & Anders

The Primitive Implementation

// ...
   @Override
   public String toString() {
      return toString(0);
   }

   private String toString(final int nesting) {
      String tabs = "";
      for (int i = nesting; i > 0; i--)
         tabs += "\t";

      return tabs + this.content + "\n"
         + printChildren(nesting + 1, new LinkedList(this.children));
   }

   private String printChildren(int nesting, List children) {
      String result = "";
      for (Node child : children) {
         result += child.toString(nesting);
      }
      return result;
   }
// ...

Going Stateless

Loops removed:

// ...
@Override
   public String toString() {
      return toString("");
   }

   private String toString(final String indentation) {
      return indentation + this.content + "\n"
         + printList(indentation + "\t", new LinkedList(this.children));
   }

   private String printList(String indentation, LinkedList children) {
      if (children.isEmpty()) return "";
      return children.pop().toString(indentation) + printList(indentation, children);
   }
// ...

Cloning the List is perhaps not a good thing from the performance point of view, but that wasn't the concern here; other languages can deal with that much more efficiently than Java. Anyway I've created a version without it (but with ugly integer constants instead):

// ...
   private String toString(final String indentation) {
      return indentation + content + "\n"
         + printList(indentation + "\t", children);
   }

   private String printList(String indentation, List children) {
      if (children.isEmpty()) return "";
      return children.get(0).toString(indentation)
         + printList(indentation, children.subList(1, children.size()));
   }
// ...

Appendix: The Node Class

The rest of the Node class representing the tree to be printed is the same in all our solutions:

package scotsman;

import java.util.LinkedList;
import java.util.List;

public class Node {

   private String content;
   private List children;

   public Node(String content) {
      this(content, new LinkedList());
   }

   public Node(String content, List children) {
      this.content = content;
      this.children = children;
   }

   public Node withChild(Node child) {
      children.add(child);
      return this;
   }

   // toString implementation comes here...

}

Conclusion

Functional programming is cool. Being in Oslo is cool. :-)

Tags: java