Resurrecting RestrictedSet

04 Feb 2014

While spelunking in Ruby's stdlib I came across the description and partial implementation of an interesting data structure called RestrictedSet. It behaves like a Ruby Set but also requires a block to be given (called a restriction proc) which determines if an object is eligible for membership. If the result of calling the restriction proc with a given object is falsey, the object is rejected (see my implementation: restricted_set).

# Initialize with or without an enumerable object
set = { |o| o > 0 }
set #=> #<RestrictedSet: {1, 2, 42}>
# Accessing the restriction proc
f = set.restriction_proc
p #=> false
p #=> true

RestrictedSet also accommodates restrictions which depend on the current set. If the restriction proc has an arity of 2, the current set and the object in question are yielded as the first and second arguments, respectively.

set = do |current_set, _|
  current_set.count + 1 <= 2 # Maximum of 2 objects
set << :a << :a << :b << :c
set #=> #<RestrictedSet: {:a, :b}>

Inheriting from RestrictedSet works well for creating reusable types of restricted sets. By overriding the initializer to pass a block to super, the restriction logic can be encapsulated in a class with a descriptive name.

class SymbolSet < RestrictedSet
  def initialize(enum = nil)
    super(enum) { |o| Symbol === o }
end["alpha", :beta]) #=> #<SymbolSet: {:beta}>
require 'prime'
class PrimeSet < RestrictedSet
  def initialize(enum = nil)
    super enum, &Prime.method(:prime?) # using Method#to_proc

(1..100).to_set(PrimeSet) #=> #<PrimeSet: {2, 3, 5, 7, 11, 13, 17, 19, ...}>
class NullSet < RestrictedSet
  def initialize(enum = nil)
    super(enum) { false }

NullSet[1, 'a', :b] #=> #<NullSet: {}>

Maybe someone can find a use for RestrictedSet in the real world :smile:. If you know why it was never implemented, please share. As always, pull requests welcome.

comments powered by Disqus