My goto answer when someone asks why I like Haskell so much these days is usually “I like the expressiveness and run time guarantees of Haskell”. For those who are little more interested, I would usually show the popular quick sort or merge sort implementations. I wanted a slightly more complicated, yet commonly known, example to demonstrate what I claimed. This is an attempt at coming up with such an example. And turning it into a blog post makes it available for me all the time (and for other too!!).
I choose Python and Java as other two languages as they are the ones I am fairly comfortable with and also because they are representatives of objected oriented and dynamically typed languages. I do not claim mastery over any of these languages. If you have any suggestions on making any of the these implementations more expressive, let me know and I will update the sample accordingly. Other languages are welcome too!
Edit: Here is my take on what expressiveness mean
All three versions do the same thing. Define a simple Tree type. Instead of
constructing the tree one-element-at-a-time, we provide a convenient function
fromList which takes a list and adds its elements to tree. We also provide a
way to turn the Tree back to a list by providing inorder function to
traverse the tree in-order
The tree construction happens like this: we split the list in to three parts - middle element, left-sublist and right-sublist. Then, we recursively construct left and right sub-tree with the two split parts of the list. The middle element is used at the current node. Why we do it this way? If you pass a sorted list, this will construct a binary search tree. In-order traversal on that tree should return the original sorted list back!
Haskell
| data Tree a = Empty | Node (Tree a) a (Tree a) | |
| deriving (Show) | |
| fromList :: [a] -> Tree a | |
| fromList xs | |
| | null xs = Empty | |
| | otherwise = Node (fromList x1) x (fromList x2) | |
| where (x1, x:x2) = splitAt (length xs `div` 2) xs | |
| inorder :: Tree a -> [a] | |
| inorder Empty = [] | |
| inorder (Node l x r) = inorder l ++ [x] ++ inorder r |
Python
| class Tree(object): | |
| def __init__(self, l, r, d): | |
| self.left = l | |
| self.right = r | |
| self.data = d | |
| def __str__(self): | |
| s = "(" | |
| s += str(self.left) if self.left else " Empty " | |
| s += " " + str(self.data) + " " | |
| s += str(self.right) if self.right else " Empty " | |
| s += ")" | |
| return s | |
| def inorder(self): | |
| l = self.left.inorder() if self.left else [] | |
| l += [self.data] | |
| l += self.right.inorder() if self.right else [] | |
| return l | |
| @staticmethod | |
| def fromList(items): | |
| if not items: | |
| return None | |
| (l, r) = splitAt(len(items)/2, items) | |
| return Tree(Tree.fromList(l), Tree.fromList(r[1:]), r[0]) | |
| def splitAt(n, items): | |
| return (items[:n], items[n:]) |
Java
| import java.lang.StringBuilder; | |
| import java.util.List; | |
| import java.util.Arrays; | |
| import java.util.ArrayList; | |
| class Tree<T> { | |
| private Tree<T> left; | |
| private Tree<T> right; | |
| private T data; | |
| public Tree(Tree<T> l, Tree<T> r, T d) { | |
| this.left = l; | |
| this.right = r; | |
| this.data = d; | |
| } | |
| public String toString() { | |
| StringBuilder sb = new StringBuilder("("); | |
| sb.append(left == null ? " Empty " : left.toString()); | |
| sb.append(" " + data.toString() + " "); | |
| sb.append(right == null ? " Empty " : right.toString()); | |
| sb.append(")"); | |
| return sb.toString(); | |
| } | |
| public static <T> Tree fromList(List<T> items) { | |
| if(items.isEmpty()) | |
| return null; | |
| int len = items.size(); | |
| int mid = len / 2; | |
| List<T> l = items.subList(0, mid); | |
| List<T> r = items.subList(mid+1, len); | |
| T x = items.get(mid); | |
| return new Tree(fromList(l), fromList(r), x); | |
| } | |
| public List<T> inorder() { | |
| List<T> list = new ArrayList(); | |
| list.addAll( left != null ? left.inorder() : new ArrayList()); | |
| list.add(data); | |
| list.addAll( right != null ? right.inorder() : new ArrayList()); | |
| return list; | |
| } | |
| public static void main(String[] args) { | |
| Integer [] array = {1,2,3,4,5}; | |
| List<Integer> list = Arrays.asList(array); | |
| Tree<Integer> tree = Tree.fromList(list); | |
| System.out.println(tree); | |
| System.out.println(tree.inorder()); | |
| } | |
| } |