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

Cool, so the question we were discussing was whether this is possible without the bound. It seems people often feel like it should be, but ultimately decide it's impossible. I'm convinced it can't be done!

@mattbaker can we get a problem description for your claim $300 challenge?
@leongersing why the hell is @ mentioning on gists not working? WHO BUILT THIS THING ANYWA?!

@mattbaker now it all makes sense. I'll keep working on it. 👍

@mikelikesbikes .... no comment. 😉

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. 😄