Introduction

When you first learn Haskell you can't help feeling impressed how easily algebraic types can be defined. For example, a binary tree type may be defined this way:

data Tree a = Empty | Leaf a | Node a (Tree a) (Tree a)

Node 2 (Node 7 (Leaf 2) 
               (Node 6 (Leaf 5) 
                       (Leaf 11))) 
       (Node 5 Empty 
               (Node 9 (Leaf 4) 
                       Empty))

Wouldn't it be nice to make something similar with (idiomatic) Ruby?

A first approach

Let's use a multiple-constructor class to implement a Tree with an example Tree#weight method:

class Tree
  def initialize(type, value = nil, left_tree = nil, right_tree = nil)
    @type = type
    @value = value
    @left_tree = left_tree
    @right_tree = right_tree
  end
  
  def self.empty
    Tree.new(:empty)    
  end

  def self.leaf(value)
    Tree.new(:leaf, value)
  end 

  def self.node(value, left_tree, right_tree)
    Tree.new(:node, value, left_tree, right_tree)
  end 

  # Return weight of tree (total number of non-empty nodes)
  def weight
    case @type
    when :empty then 0
    when :leaf then 1
    when :node then 1 + @left_tree.weight + @right_tree.weight
    end  
  end 
end

To be used this way:

tree = Tree.node(1, Tree.leaf(2), 
                    Tree.node(3, Tree.empty, 
                                 Tree.leaf(4)))

p tree.weight #=> 4

Full code: manual.rb

Abstracting

The previous code is too verbose, and there is clearly some boilerplate we could abstract. That's the best I was able to came up with:

class Tree
  include ADT
  constructor :empty
  constructor :leaf => :value
  constructor :node => [:value, :left_tree, :right_tree]  
end

Granted, it has not the beauty of Haskell, but it looks pretty idiomatic and clear. As usual with Ruby, no type-checking is performed (though it could be easily added)

Full code: adt.rb, adt_tree.rb, adt_tree_test.rb