
Ruby is cool
22/06/2015
Source(first version)
Do you think this title is ridiculous ? I do. But last week I gave my first try to Ruby, and I have nothing really useful to share: this blog post is just the story of someone discovering Ruby.
I was looking for a (cool) programming language providing a way to deal with sets. The set library perfectly fulfilled my expectation :
>> require "set" >> s1 = ["a", "b"].to_set >> puts s1.inspect #<Set: {"a", "b"}> >> s2 = ["b", "c"].to_set >> puts s2.inspect #<Set: {"b", "c"}> >> puts s1.subset? s2 false >> puts s1.union(s2).inspect #<Set: {"a", "b", "c"}>
Is there something to explain in the above code ? I don’t think so (unless you have never used any programming language). And this one of the reasons for which Ruby is cool.
Settheoretic construction of natural numbers
In order to train myself to use the Ruby langage, I undertook to implement the settheoretic construction of the natural numbers: \[0 = \{\varnothing\}, \quad 1=0 \cup \{0\}= \{\varnothing, \{\varnothing\}\}, \quad 2=1\cup\{1\}=\{\varnothing, \{\varnothing\}, \{\varnothing, \{\varnothing\}\}\}, \quad ...\]
To define \(0\) we can use \(\varnothing\) as a character or as a symbol:
>> puts ["Ø"].to_set.inspect #<Set: {"Ø"}> >> puts [:Ø].to_set.inspect #<Set: {:Ø}>
Now, we define a recursive function calculating the set representation of an integer:
>> def set_representation(n) n == 0 ? ["Ø"].to_set : set_representation(n1).tap {x break x.union([x].to_set)} end
See this stackoverflow thread about the usage of
tap
to map a single object to a function.The
set_representation
function works fine:>> puts set_representation(1).inspect #<Set: {"Ø", #<Set: {"Ø"}>}> >> puts set_representation(2).inspect #<Set: {"Ø", #<Set: {"Ø"}>, #<Set: {"Ø", #<Set: {"Ø"}>}>}>
However, another way consists in using a hash, as I learnt by reading Algorithmic Fun with Ruby Hashes. The code is similar to the one of
set_representation
, except that the first value must be initialized outside the body:>> set_hash = Hash.new do hash,n hash[n] = hash[n1].tap {x break x.union([x].to_set)} end >> # initialization: >> set_hash[0] = ["Ø"].to_set
Results, as expected, are the same:
>> puts set_hash[2].inspect #<Set: {"Ø", #<Set: {"Ø"}>, #<Set: {"Ø", #<Set: {"Ø"}>}>}>
And the computation times are comparable:
>> # time consumed by the function: >> start = Time.now; set_representation(15); finish = Time.now >> puts finish  start 0.083684302 >> # time consumed by the hash: >> start = Time.now; set_hash[15]; finish = Time.now >> puts finish  start 0.082218561
But look what happens if I rerun the same code:
>> # time consumed by the function: >> start = Time.now; set_representation(15); finish = Time.now >> puts finish  start 0.080877005 >> # time consumed by the hash: >> start = Time.now; set_hash[15]; finish = Time.now >> puts finish  start 8.97e07
Now, the time consumed by
set_hash[15]
is almost instantaneous! This is due to memoization (see Algorithmic Fun with Ruby Hashes).Displaying a set
My next goal was to get a better rendering of the sets. Indeed, it is hard to read something like :
>> puts set_hash[2].inspect #<Set: {"Ø", #<Set: {"Ø"}>, #<Set: {"Ø", #<Set: {"Ø"}>}>}>
as compared to \[\{\varnothing, \{\varnothing\}, \{\varnothing, \{\varnothing\}\}\}\] isn’t it ? Then I defined a recursive hash:
>> display_hash = Hash.new do hash,set if set.inject(true) {status, x status and x.class==String} display_hash[set] = "{" + set.inject {union, x union + "," + x} + "}" else set = set.to_a for i in 0 .. set.size1 if set[i].class == Set set[i] = display_hash[Set.new(set[i])] end end display_hash[set] = display_hash[set.to_set] end end
The first line checks whether all elements of the set are some strings. If so, it returns the set as a character string with a comma separating the elements and some braces. Otherwise, the hash is calculated for each element of the set which are themselves some sets (the procedure assumes that the set to be displayed consists only of character strings and of sets of such sets). And it works as desired:
>> one = set_hash[1] >> two = set_hash[2] >> three = set_hash[3] >> puts one.inspect # ugly #<Set: {"Ø", #<Set: {"Ø"}>}> >> puts display_hash[one] # beautiful {Ø,{Ø}} >> puts two.inspect # ugly #<Set: {"Ø", #<Set: {"Ø"}>, #<Set: {"Ø", #<Set: {"Ø"}>}>}> >> puts display_hash[two] # beautiful {Ø,{Ø},{Ø,{Ø}}} >> puts three.inspect # ugly #<Set: {"Ø", #<Set: {"Ø"}>, #<Set: {"Ø", #<Set: {"Ø"}>}>, #<Set: {"Ø", #<Set: {"Ø"}>, #<Set: {"Ø", #<Set: {"Ø"}>}>}>}> >> puts display_hash[three] # beautiful {Ø,{Ø},{Ø,{Ø}},{Ø,{Ø},{Ø,{Ø}}}}
The memoization offered by the hash approach has a great advantage here. Take for example the case of \(2\): \[2 = \{\varnothing, \{\varnothing\}, \{\varnothing, \{\varnothing\}\}\} = \{\varnothing, \{\varnothing\}, 1\},\] and then, when the set representation of \(2\) is generated, the set representation of \(1\) is generated as well, and this one is memoized. For example we can see that the time consumed by
set_hash[16]
is almost instantaneous onceset_hash[17]
is calculated:>> # time consumed by set_hash[17]: >> start = Time.now; set_hash[17]; finish = Time.now >> puts finish  start 0.243370526 >> # time consumed by set_hash[16]: >> start = Time.now; set_hash[16]; finish = Time.now >> puts finish  start 1.14e06
Unordered pairs
Finally, I wanted to visualize the iterated unordered pairs of a set. That is, starting for example from the set \(A_1=\{a,b\}\), the set of its unordered pairs is \(A_2 = \{\{a\}, \{a,b\}, \{b\}\}\), then we form the set of unordered pairs of \(A_2\), and so on. A simple function does this job:
>> def pairs(s,n) while n > 0 do b = s.to_a s = [].to_set for i in 0 .. b.size1 for j in i .. b.size1 s.add([b[i],b[j]].to_set) end end n = n  1 end return s.to_set end
And the rendering hash works fine:
>> p1 = pairs(["a","b"].to_set, 1) >> puts display_hash[p1] {{a},{a,b},{b}} >> p2 = pairs(["a","b"].to_set, 2) >> puts display_hash[p2] {{{a}},{{a},{a,b}},{{a},{b}},{{a,b}},{{a,b},{b}},{{b}}}
We can also list the iterated pairs using
map
:>> p3 = pairs(["a","b"].to_set, 3) >> puts p3.map {x display_hash[x]} {{{a}}} {{{a}},{{a},{a,b}}} {{{a}},{{a},{b}}} {{{a}},{{a,b}}} {{{a}},{{a,b},{b}}} {{{a}},{{b}}} {{{a},{a,b}}} {{{a},{a,b}},{{a},{b}}} {{{a},{a,b}},{{a,b}}} {{{a},{a,b}},{{a,b},{b}}} {{{a},{a,b}},{{b}}} {{{a},{b}}} {{{a},{b}},{{a,b}}} {{{a},{b}},{{a,b},{b}}} {{{a},{b}},{{b}}} {{{a,b}}} {{{a,b}},{{a,b},{b}}} {{{a,b}},{{b}}} {{{a,b},{b}}} {{{a,b},{b}},{{b}}} {{{b}}}
Now, maybe you still think the title is ridiculous. But I hope you believe Ruby is cool.