-
-
Save leongersing/576a20a48e6a5270b2fc to your computer and use it in GitHub Desktop.
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 |
@ndelage, I was under the same impression. Map needs to return a set (function), given a set (function) and an expression.
Correct. Here's the signature for map
from the assignment.
type Set = Int => Boolean
def map(s: Set, f: Int => Int): Set
Oh, well the assignment made this MUCH EASIER TO pull off. First off, the iterative methods are linearly iterative and meant to run against bounded sets. Second, having method signatures for the functions we're building helped reign in my previous attempt. Please review my next revision.
@ndelage added your specs to the suite. π
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. π
From my understanding of the problem, I'd expect the map function to return a set function that when called, returns true or false. I tried running the following test, but calling the return value of
map
returns a lambda. What am I missing?