Harry R. Schwartz

I take a certain amount of perverse pleasure in using Ruby to do things that don’t really suit it. Here’s another example: implementing a set using only function calls.

class FunctionSet
  def initialize(fun = ->(_) { false })
    @fun = fun
  end

  def include?(obj)
    fun.call(obj)
  end

  def add(new_obj)
    rest = fun
    @fun = ->(obj) { obj == new_obj || rest.call(obj) }
  end

  def union(other)
    fun_self = fun
    fun_other = other.fun

    self.class.new(
      ->(obj) { fun_self.call(obj) || fun_other.call(obj) }
    )
  end

  protected

  attr_reader :fun
end

Get it? Inserting a new element into the set essentially prefixes a clause onto an ever-growing Boolean expression, while testing for inclusion is equivalent to evaluating the expression.

So, for example, let’s create a set and add a few elements to it, along with some comments illustrating the current state of fun:

set = FunctionSet.new
# ->(_) { false }

set.insert(5)
# ->(obj) { obj == 5 || false }

set.insert(7)
# ->(obj) { obj == 7 || obj == 5 || false }

set.insert(9)
# ->(obj) { obj == 9 || obj == 7 || obj == 5 || false }

That’s a terrifically inefficient set representation, of course—checking inclusion is linear, for one thing, and every element adds another stack frame to the inclusion check, which’ll blow it eventually—but, still, pretty cute!

We could also add a #delete method, if we’d like, which removes an element from the set. We can’t just append another clause onto the front of the disjunct, since it’ll need to short-circuit the calls by returning false. We’ll need a real conditional.

def delete(new_obj)
  rest = fun
  @fun = lambda { |obj|
    if obj == new_obj
      false
    else
      rest.call(obj)
    end
  }
end

set = FunctionSet.new
set.insert(5)
set.insert(7)
set.delete(5)

# -> (obj) {
#   if obj == 5
#     false
#   else
#     obj == 7 || obj == 5 || false
#   end
# }

set.include?(7) # => true
set.include?(5) # => false

Notice that deleting an element interrupts the evaluation of the Boolean expression, ensuring that we’ll never reach the previously inserted value. We could also insert 5 again, of course, and evaluating that expression would return true before reaching the conditional.

set.insert(5)
set.insert(7)
set.delete(5)
set.insert(5)

# -> (obj) {
#   obj == 5 || if obj == 5
#     false
#   else
#     obj == 7 || obj == 5 || false
#   end
# }

set.include?(5) # => true

If you think this kind of thing is fun, you might take a stab at extending FunctionSet by implementing #complement, #intersection, and #difference methods.