Print Dendrogram In Ruby
After waddling through a lot of Java code during the week, I decided to unwind in the weekend with Ruby code. And a favourite pastime is to convert Python code to Ruby code.
I took one program, Dendrogram drawing -- a Python recipe, from the site code.activestate.com. What the program does is, to "Print dendrogram of a binary tree. Each tree node is represented by a length-2 tuple." When I read it first time, I too didn't understand fully as to what it does. In order to spare some of you the same agony, let's break down the quoted objective into key terms and get their meanings.
First, the menacing sounding word dendrogram. I bet that for a lot of you, this is the first time you are encountering this word. From dictionary.com, we get to know that it is "a treelike diagram depicting evolutionary changes from ancestral to descendant forms, based on shared characteristics." From the same website, we get the British Dictionary definition as, "any branching diagram, such as a cladogram, showing the interconnections between treelike organisms." Okay, okay, it's a diagram that has its roots (pun intended) in biology.
Next, a binary tree. To refresh ourselves about it, we go through the meaning of a
tree --> ordered tree --> binary tree, as follows:
A tree is an abstract data type that stores elements hierarchically. With the exception of the top element, each element in a tree has a parent element and zero or more children elements.
A tree is ordered if there is a linear ordering defined for the children of each node; that is, we can identify children of a node as being the first, second, third, and so on.
A binary tree is an ordered tree with the following properties:
1. Every node has at most two children.
2. Each child node is labeled as being either a left child or a right child.
3. The left child precedes the right child in the ordering of the children of a node.
[Source : Data Structures and Algorithms in Java, Third Edition by Goodrich and Tamassia, Wiley India (P) Ltd, 2004.]
And, finally, a 2-tuple in Python means an immutable array with two members.
Now I think we have a fair understanding of what the program does, which, to reiterate is to print dendrogram of a binary tree, where each node is represented by a 2-length tuple.
Take a look at the Python code --
The interesting thing is, it has a function that has another function inside it which calls itself recursively. You are a pure computer science techie, if you think induction and code using recursion. In your coding and your daily life. Don't look at me strangely when I say use recursion in your daily life. Christopher Nolan has used it in his short film and his feature film Inception.
But then, Ruby doesn't allow function in a function. So how do you translate this program into Ruby? Lo, lambdas to the rescue. To put very briefly, lambdas are anonymous functions. However, you would invoke a normal function with just the function name and its parameters. But for a lambda, you assign it to a name and then invoke .call on that name. See the following example:
When you call the function outer with argument 5, outer calls a lambda with arguments 5 and 6, that adds them and prints the result 11.
Now, the question is, why do you really want to write a function within another function? I really don't have a good answer for this, except that you get a good top-down readability. If you have better reasons, please do let me know. Maybe there's something in the program's lookup table and some such thing, I don't know.
Anyways, with the problem of function in a function sorted out, there were a few other syntactic hurdles in porting the program to Ruby. I have given the Python snippet and the Ruby equivalents below:
Python:
Python:
Python:
Python:
Python:
Here is the complete Ruby code:
In both cases, whether you run the Python program or Ruby program, you will get the same output as follows:
I took one program, Dendrogram drawing -- a Python recipe, from the site code.activestate.com. What the program does is, to "Print dendrogram of a binary tree. Each tree node is represented by a length-2 tuple." When I read it first time, I too didn't understand fully as to what it does. In order to spare some of you the same agony, let's break down the quoted objective into key terms and get their meanings.
First, the menacing sounding word dendrogram. I bet that for a lot of you, this is the first time you are encountering this word. From dictionary.com, we get to know that it is "a treelike diagram depicting evolutionary changes from ancestral to descendant forms, based on shared characteristics." From the same website, we get the British Dictionary definition as, "any branching diagram, such as a cladogram, showing the interconnections between treelike organisms." Okay, okay, it's a diagram that has its roots (pun intended) in biology.
Next, a binary tree. To refresh ourselves about it, we go through the meaning of a
tree --> ordered tree --> binary tree, as follows:
A tree is an abstract data type that stores elements hierarchically. With the exception of the top element, each element in a tree has a parent element and zero or more children elements.
A tree is ordered if there is a linear ordering defined for the children of each node; that is, we can identify children of a node as being the first, second, third, and so on.
A binary tree is an ordered tree with the following properties:
1. Every node has at most two children.
2. Each child node is labeled as being either a left child or a right child.
3. The left child precedes the right child in the ordering of the children of a node.
[Source : Data Structures and Algorithms in Java, Third Edition by Goodrich and Tamassia, Wiley India (P) Ltd, 2004.]
And, finally, a 2-tuple in Python means an immutable array with two members.
Now I think we have a fair understanding of what the program does, which, to reiterate is to print dendrogram of a binary tree, where each node is represented by a 2-length tuple.
Take a look at the Python code --
The interesting thing is, it has a function that has another function inside it which calls itself recursively. You are a pure computer science techie, if you think induction and code using recursion. In your coding and your daily life. Don't look at me strangely when I say use recursion in your daily life. Christopher Nolan has used it in his short film and his feature film Inception.
But then, Ruby doesn't allow function in a function. So how do you translate this program into Ruby? Lo, lambdas to the rescue. To put very briefly, lambdas are anonymous functions. However, you would invoke a normal function with just the function name and its parameters. But for a lambda, you assign it to a name and then invoke .call on that name. See the following example:
When you call the function outer with argument 5, outer calls a lambda with arguments 5 and 6, that adds them and prints the result 11.
Now, the question is, why do you really want to write a function within another function? I really don't have a good answer for this, except that you get a good top-down readability. If you have better reasons, please do let me know. Maybe there's something in the program's lookup table and some such thing, I don't know.
Anyways, with the problem of function in a function sorted out, there were a few other syntactic hurdles in porting the program to Ruby. I have given the Python snippet and the Ruby equivalents below:
Python:
return type(T) == tuple and len(T) == 2
Ruby:return t.class == Array && t.length == 2
Python:
s = list(str(T))
Ruby:s = t.chars
Python:
del activeLevels[h]
Ruby:activeLevels.delete(h)
Python:
A = list(activeLevels)
Ruby:a = activeLevels.keys
Python:
print (''.join(s))
Ruby:puts s.join("")
Here is the complete Ruby code:
In both cases, whether you run the Python program or Ruby program, you will get the same output as follows:
Comments
Post a Comment