1. Ruby is cool


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

    Set-theoretic construction of natural numbers

    In order to train myself to use the Ruby langage, I undertook to implement the set-theoretic 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(n-1).tap {|x| break x.union([x].to_set)} 

    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[n-1].tap {|x| break x.union([x].to_set)}
    >> # 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
    >> # time consumed by the hash:
    >> start = Time.now; set_hash[15]; finish = Time.now
    >> puts finish - start

    But look what happens if I re-run the same code:

    >> # time consumed by the function:
    >> start = Time.now; set_representation(15); finish = Time.now
    >> puts finish - start
    >> # time consumed by the hash:
    >> start = Time.now; set_hash[15]; finish = Time.now
    >> puts finish - start

    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} + "}"
        set = set.to_a
        for i in 0 .. set.size-1
          if set[i].class == Set 
            set[i] = display_hash[Set.new(set[i])]
        display_hash[set] = display_hash[set.to_set] 

    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 once set_hash[17] is calculated:

    >> # time consumed by set_hash[17]:
    >> start = Time.now; set_hash[17]; finish = Time.now
    >> puts finish - start
    >> # time consumed by set_hash[16]:
    >> start = Time.now; set_hash[16]; finish = Time.now
    >> puts finish - start

    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.size-1
                for j in i .. b.size-1
            n = n - 1
        return s.to_set

    And the rendering hash works fine:

    >> p1 = pairs(["a","b"].to_set, 1)
    >> puts display_hash[p1]
    >> p2 = pairs(["a","b"].to_set, 2)
    >> puts display_hash[p2]

    We can also list the iterated pairs using map:

    >> p3 = pairs(["a","b"].to_set, 3)
    >> puts p3.map {|x| display_hash[x]}

    Now, maybe you still think the title is ridiculous. But I hope you believe Ruby is cool.