This article gives a simple purely functional sorted, unbalanced tree structure in 67 lines of java. The direct Haskell translation below is 13 lines; Java's verbosity ratio is 5.15.
data (Ordered a) => SortedSet a = Empty | Node (SortedSet a) a (SortedSet a)
contains :: a -> SortedSet a -> Bool
contains _ Empty = False
contains x (Node left y right) | x < y = contains x left
| x > y = contains x right
| otherwise = True
add :: a -> SortedSet a -> SortedSet a
add x Empty = Node Empty x Empty
add x s@(Node left y right) | x < y = Node (add x left) y right
| x > y = Node left y (add x right)
| otherwise = s
The original code:
interface Ordered <T> {
public boolean isLessThan(T that) ;
}
abstract class SortedSet<T extends Ordered<T>> {
public abstract boolean isEmpty() ;
public abstract boolean contains(T element) ;
public abstract SortedSet<T> add(T element) ;
public static final <E extends Ordered<E>> SortedSet<E> empty() {
return new EmptySet<E>();
}
}
final class EmptySet<T extends Ordered<T>> extends SortedSet<T> {
public boolean isEmpty() {
return true ;
}
public boolean contains(T element) {
return false ;
}
public SortedSet<T> add(T element) {
return new Node<T>(this,element,this) ;
}
public EmptySet() {
}
}
final class Node<T extends Ordered<T>> extends SortedSet<T> {
private final SortedSet<T> left ;
private final T element ;
private final SortedSet<T> right ;
public boolean isEmpty() {
return false ;
}
public Node(SortedSet<T> left, T element, SortedSet<T> right) {
this.left = left ;
this.right = right ;
this.element = element ;
}
public boolean contains(T needle) {
if (needle.isLessThan(this.element)) {
return this.left.contains(needle) ;
} else if (this.element.isLessThan(needle)) {
return this.right.contains(needle) ;
} else {
return true ;
}
}
public SortedSet<T> add(T newGuy) {
if (newGuy.isLessThan(this.element)) {
return new Node<T>(left.add(newGuy),this.element,right) ;
} else if (this.element.isLessThan(newGuy)) {
return new Node<T>(left,this.element,right.add(newGuy)) ;
} else {
return this ; // Already in set.
}
}
}