# Harry R. Schwartz

Software engineer, nominal scientist, gentleman of the internet. Member, ←Hotline Webring→.

### Implementing Sets with Functions

Published . Tags: puzzles, ruby.

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

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

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.