Function Sets in Ruby

set.rb

set       = ->(int){ int > -1000 && int < 1000 }
contains  = ->(setFn, int){ setFn.(int) }

sset      = ->(y){ ->(x){ x == y } }

union     = ->(s1, s2){ ->(x){ s1.(x) || s2.(x) } }
intersect = ->(s1, s2){ ->(x){ s1.(x) && s2.(x) } }
diff      = ->(s1, s2){ ->(x){ s1.(x) && !s2.(x) } }
filter    = ->(s, p){ ->(x){ p.(x) && s.(x) } }


# forall is bounded by the rules of the docs... 
# "Here, we consider that an integer x has the property -1000 <= x <= 1000 in order to limit the search space."

ubound = 1000
lbound = -1000

forall = ->(s, p){
  iter = ->(x){
      if x > ubound
        return true
      elsif contains.(s, x)
        return false unless p.(x)
      end
      iter.(x+1)
    }
  iter.(lbound)
}

exists = ->(s, p){
  iter = ->(x){
      if x > ubound
        return false
      elsif contains.(s, x)
        return true if p.(x)
      end
      iter.(x+1)
    }
  iter.(lbound)
}

map = ->(s, f){
  iter = ->(ms, x){
      if x > ubound
        return ms.nil? ? ->(x){ false } : ms
      elsif s.(x)
        new_set = ms.nil? ? sset.(f.(x)) : union.(ms, sset.(f.(x)))
        iter.(new_set, x+1)
      else
        iter.(ms, x+1)
      end
    }
  iter.(nil, lbound)
}


describe "functional sets" do

  it "set" do
    expect( set.(1) ).to eq true
  end

  it "singleton_set" do
    set1 = sset.(1)

    expect( contains.(set1, 1) ).to eq true
    expect( contains.(set1, 2) ).to eq false
  end

  it "union" do
    expect( contains.( union.( sset.(1), sset.(2) ), 1 ) ).to eq true
    expect( contains.( union.( sset.(1), sset.(2) ), 2 ) ).to eq true
    expect( contains.( union.( sset.(1), sset.(2) ), 3 ) ).to eq false
  end

  it "union of union" do
    u1t4 = union.( union.( sset.(1), sset.(2) ), union.( sset.(3), sset.(4) ) )
    expect( contains.(u1t4, 0) ).to eq false
    expect( contains.(u1t4, 1) ).to eq true
    expect( contains.(u1t4, 2) ).to eq true
    expect( contains.(u1t4, 3) ).to eq true
    expect( contains.(u1t4, 4) ).to eq true
    expect( contains.(u1t4, 5) ).to eq false
  end

  it "intersect" do
    s1n2 = union.( sset.(1), sset.(2) )
    s1t4 = union.( s1n2, union.( sset.(3), sset.(4) ) )
    expect( contains.( intersect.( s1n2, s1t4 ), 1) ).to eq true
    expect( contains.( intersect.( s1n2, s1t4 ), 2) ).to eq true
    expect( contains.( intersect.( s1n2, s1t4 ), 3) ).to eq false
    expect( contains.( intersect.( s1n2, s1t4 ), 4) ).to eq false
  end

  it "diff" do
    s1n2 = union.( sset.(1), sset.(2) )
    s1n3 = union.( sset.(1), sset.(3) )
    expect( contains.( diff.( s1n2, s1n3 ), 1) ).to eq false
    expect( contains.( diff.( s1n2, s1n3 ), 2) ).to eq true
    expect( contains.( diff.( s1n2, s1n3 ), 3) ).to eq false
  end

  it "filter" do
    s1t4 = union.( union.( sset.(1), sset.(2) ), union.( sset.(3), sset.(4) ) )
    s2n4 = filter.( s1t4, ->(x){ x.even? } )
    expect( contains.(s2n4, 1) ).to eq false
    expect( contains.(s2n4, 2) ).to eq true
    expect( contains.(s2n4, 3) ).to eq false
    expect( contains.(s2n4, 4) ).to eq true
  end

  it "forall" do
    s1t4 = union.( union.( sset.(1), sset.(2) ), union.( sset.(3), sset.(4) ) )

    expect( forall.( s1t4, ->(x){ x > 0 } ) ).to eq true
    expect( forall.( s1t4, ->(x){ x < 0 } ) ).to eq false
  end

  it "exists" do
    s1t4 = union.( union.( sset.(1), sset.(2) ), union.( sset.(3), sset.(4) ) )

    expect( exists.( s1t4, ->(x){ x.even? } ) ).to eq true
    expect( exists.( s1t4, ->(x){ x.odd? } ) ).to eq true
    expect( exists.( s1t4, ->(x){ x.zero? } ) ).to eq false
  end

  it "maps" do
    s1t4 = union.( union.( sset.(1), sset.(2) ), union.( sset.(3), sset.(4) ) )

    expect( map.(s1t4, ->(x){ x * 2 }).(1) ).to eq false
    expect( map.(s1t4, ->(x){ x * 2 }).(2) ).to eq true
    expect( map.(s1t4, ->(x){ x * 2 }).(3) ).to eq false
    expect( map.(s1t4, ->(x){ x * 2 }).(4) ).to eq true
    expect( map.(s1t4, ->(x){ x * 2 }).(5) ).to eq false
    expect( map.(s1t4, ->(x){ x * 2 }).(6) ).to eq true
    expect( map.(s1t4, ->(x){ x * 2 }).(7) ).to eq false
    expect( map.(s1t4, ->(x){ x * 2 }).(8) ).to eq true
  end

  it "maps maps" do
    s1t4 = union.( union.( sset.(1), sset.(2) ), union.( sset.(3), sset.(4) ) )
    my_set = map.( map.(s1t4, ->(x){ x * 2 }), ->(x){ x * x } )

    expect( my_set.(4) ).to eq true
    expect( my_set.(16) ).to eq true
    expect( my_set.(36) ).to eq true
    expect( my_set.(64) ).to eq true
    expect( my_set.(100) ).to eq false
  end

  it "passes Nate's test" do
    nset = ->(x){ [1,2,3].include? x }

    expect( nset.(0) ).to eq false
    expect( nset.(1) ).to eq true
    expect( nset.(2) ).to eq true
    expect( nset.(3) ).to eq true
    expect( nset.(4) ).to eq false

    mapped_set = map.( nset, ->(x){ x * 2 })
    expect( mapped_set.(0) ).to eq false
    expect( mapped_set.(1) ).to eq false
    expect( mapped_set.(2) ).to eq true
    expect( mapped_set.(3) ).to eq false
    expect( mapped_set.(4) ).to eq true
    expect( mapped_set.(5) ).to eq false
    expect( mapped_set.(6) ).to eq true
    expect( mapped_set.(7) ).to eq false
    expect( mapped_set.(8) ).to eq false
  end

end

Pretty sure that $300 bounty (gulp! this is getting real) was for an unbounded set.

yeah, I was so 🍻 🍻 🍻 I couldn't remember what the hell we agreed to. ATM this is my favorite happy distraction. 😄