### Algebraic data types (unions) in Ruby

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]
```