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]