### Algebraic data types (unions) in Ruby

Posted on September 20, 2013

Let’s consider a simple tree defined in Haskell as

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

Naive Ruby’s approach would be defining a class `Node` and assuming node is a leaf when both left and right sub-trees are `nil` (i. e. `nil` is representing an empty tree):

``````class Node
def initialize(v, left, right)
@v, @left, @right = v, left, right
end

def each(&block)
@left.each(&block) if @left
block[@v]
@right.each(&block) if @right
end
end``````

But it doesn’t work well. First of all `if @left` is not a good recursive approach, but more importantly there is no standalone representation of an empty tree. But unions can be represented by using inheritance:

``````class Tree
def self.empty
Empty.new
end

def flatten
vs = []
each do |v|
vs << v
end
vs
end
end

class Empty < Tree
def each
end

def append(v)
Node.new(v, Tree.empty, Tree.empty)
end
end

class Node < Tree
def initialize(v, left, right)
@v, @left, @right = v, left, right
end

def each(&block)
@left.each(&block)
block[@v]
@right.each(&block)
end

def append(v)
if v < @v
Node.new(@v, @left.append(v), @right)
elsif v > @v
Node.new(@v, @left, @right.append(v))
else
self
end
end
end

Tree.empty.append(1).append(0).append(3).flatten
#=> [0, 1, 3]``````

Now I can add a bunch of methods to the `Tree` class based on `each`, e. g. `map`. I don’t want to include `Enumerable` because that `map` will return me an array, but what I really want is the same data structure, i. e. `Tree`.

``````class Tree

...

def fmap(&block)
r = self.class.empty
each do |v|
r = r.append(block[v])
end
r
end
end

p Tree.empty.append(1).append(0).append(3).fmap { |x| - x }.flatten
#=> [-3, -1, 0]``````

Meanwhile the implementation of `fmap` is based on two methods: `self.empty` and `append`, so if I define those methods for any other class I can get `fmap` for free (I will rename them to `fempty` and `fappend` so I don’t clash with Ruby names). I have always wondered why map over a `Hash` returns an `Array` while it should have returned a `Hash`:

``````module Functor
def fmap(&block)
r = self.class.fempty
each do |v|
r = r.fappend(block[v])
end
r
end
end

class Hash
include Functor

class << self
alias :fempty :new
end

# Not very functional
def fappend(kv)
k, v = kv
self[k] = v
self
end
end

{ :a => 1 }.fmap { |k, v| [k, 3] }
#=> {:a => 3}``````

Linked list can be defined in a similar fashion:

``````class List
include Functor

class << self
alias :fempty :new
end

def to_a
xs = []
each do |x|
xs << x
end
xs
end
end

class Empty < List
def each
end

def fappend(v)
Cons.new(v, List.fempty)
end
end

class Cons < List
def initialize(h, t)
@h, @t = h, t
end

def each(&block)
block[@h]
@t.each(&block)
end

def fappend(v)
Cons.new(v, self)
end
end

List.fempty.fappend(1).fappend(2).fmap{ |x| x + 1 }.to_a
#=> [2, 3]``````