Including a module in Ruby

18 11 2007

If we define two modules, with methods that have the same names

module M1
  def foo
    puts "M1"
  end
end

module M2
  def foo
    puts "M2"
  end
end

and then include them in a class in a specific order

class C
  include M1
  include M2
end

method from the last included module will be used.

C.new.foo # => "M2"

So it looks like the methods are “copied” into the including class, so that the last definition of “foo” gets precedence. That’s how I thought about including Ruby modules initially.

But if that was the case the following example

module M
  def foo
    puts "M"
  end
end

class C
  def foo
    puts "C"
  end
  include M
end

should print “M”. But it doesn’t.

C.new.foo # => "C"

It calls the class “C” version of the “foo”, so the method can’t be redefined during the include.

What actually happens (and what I learned from “Include” part of Chapter 4 of Ruby Hacking Guide) is that the included module gets injected into the class hierarchy right above “C”.

class C
  def foo
    puts "C"
    super # Calling to see what the superclass defined.
  end
end

Let’s check what the hierarchy looks like before the inclusion of M.

C.ancestors # => [C, Object, Kernel]

Now let’s define “M”

module M
  def foo
    puts "M"
  end
end

and include it in “C”.

class C
  include M
end

Let’s check how it affected the class hierarchy.

C.ancestors # => [C, M, Object, Kernel]

Module “M” got injected as a direct superclass of “C”.

C.new.foo # => "C" then "M"

As C#foo calls super it’s now obvious how we got that output.

Advertisements




Solution to Code Kata Fifteen

5 11 2007

Just felt like doing some programming exercise. My bookmarks led me to the code kata 15. First, the problem:

Think of binary numbers: sequences of 0’s and 1’s. How many n-digit binary numbers are there that don’t have two adjacent 1 bits? For example, for three-digit numbers, five of the possible eight combinations meet the criteria: 000, 001, 010, 011, 100, 101, 110, 111. What is the number for sequences of length 4, 5, 10, n?

Having worked out the pattern, there’s a second part to the question: can you prove why that relationship exists?

Now, the solution.

Let’s call the function that calculate the number of n-digit binary numbers without two adjacent 1 bits a(n).

Now let’s define two helper functions. a0(n) returns number of those binary numbers that end with zero, and a1(n) returns number of those ending with one. Thus, it’s obvious that:

a(n) = a0(n) + a1(n)

Now, suppose we already have a set of (n-1)-bit numbers generated and now, based on that, we want to generate a new set of n-bit numbers. We’ll do that by adding a single bit to the end of each (n-1)-bit number. Because we care only about adjacent 1s, we can add 0s to the end of every (n-1)-bit number. Thus:

a0(n) = a(n-1)

On the other hand we can’t add 1s to each (n-1)-bit number. We can only add 1 to numbers which had 0 at the end. Thus:

a1(n) = a0(n-1)

By simple substitution we can rewrite the last equation into the following one:

a1(n) = a(n-2)

Get back to the definition of a0(n) and a1(n) and make the final substitution:

a(n) = a(n-1) + a(n-2)

Doesn’t it look familiar? Now you only have to say that a(1) = 2 and a(2) = 3 and you’re done.