Recursion with blocks

Ruby
1

I have a tree structure where I want to walk the structure and find a
node based on a name. I’m unclear how to use recursion with blocks such
that I can return the correct node. All code snippets I’ve seen have
involved using “puts” to print out a node i.e. not returning anything to
the top-level caller. What’s the idiomatic Ruby for doing this? How do
I return a value from a block called recursively?

2

On Nov 13, 2007 4:49 PM, Mike P. [email protected] wrote:

I have a tree structure where I want to walk the structure and find a
node based on a name. I’m unclear how to use recursion with blocks such
that I can return the correct node. All code snippets I’ve seen have
involved using “puts” to print out a node i.e. not returning anything to
the top-level caller. What’s the idiomatic Ruby for doing this? How do
I return a value from a block called recursively?

Posted via http://www.ruby-forum.com/.

A Ruby block is no different from a regular method. The result of the
last
line of the block is returned unless there’s a manual “return” eariler
in
the code.

Jason

3

On Nov 13, 2007, at 3:49 PM, Mike P. wrote:

I have a tree structure where I want to walk the structure and find a
node based on a name. I’m unclear how to use recursion with blocks
such
that I can return the correct node. All code snippets I’ve seen have
involved using “puts” to print out a node i.e. not returning
anything to
the top-level caller. What’s the idiomatic Ruby for doing this?
How do
I return a value from a block called recursively?

Does this give you some ideas?

#!/usr/bin/env ruby -wKU

class Tree
def initialize(name)
@name = name
@leaves = Array.new
end

attr_reader :name

def <<(leaf_name)
@leaves << self.class.new(leaf_name)
self
end

include Enumerable

def each(&block)
block[self]
@leaves.each { |leaf| leaf.each(&block) }
end

def to_s(indent = String.new)
str = “#{indent}#{@name}\n”
@leaves.each { |leaf| str += leaf.to_s(indent + " ") }
str
end
end

tree = Tree.new(“top”)
tree << “left” << “right”

tree.find { |leaf| leaf.name == “right” } << “deep”

puts tree

END

James Edward G. II

4

Sort of. I’m still unclear how the actual node is propagated back up as
the result of the find call due to the name == “right” block returning
true.

Now how do I put this on a class which is an ActiveRecord (i.e. the find
method is already taken)?

BTW Saw your talk at the LSRC. I was very inspired to use Ruby for
everything gluey. :slight_smile:

James G. wrote:

Does this give you some ideas?

#!/usr/bin/env ruby -wKU

class Tree
def initialize(name)
@name = name
@leaves = Array.new
end

attr_reader :name

def <<(leaf_name)
@leaves << self.class.new(leaf_name)
self
end

include Enumerable

def each(&block)
block[self]
@leaves.each { |leaf| leaf.each(&block) }
end

def to_s(indent = String.new)
str = “#{indent}#{@name}\n”
@leaves.each { |leaf| str += leaf.to_s(indent + " ") }
str
end
end

tree = Tree.new(“top”)
tree << “left” << “right”

tree.find { |leaf| leaf.name == “right” } << “deep”

puts tree

END

James Edward G. II

5

Ok, that I understand. You aren’t actually recursing inside the block,
just using the block as a conditional. I was trying to figure out how
to recurse inside the block.

6

On Nov 13, 2007, at 5:12 PM, Mike P. wrote:

Sort of.

We’ll get there…

I’m still unclear how the actual node is propagated back up as
the result of the find call due to the name == “right” block returning
true.

We’re calling a block recursively, just as we would a method. The
typical trick for getting a result from that is just to hand a return
value back up the call stack. For example:

#!/usr/bin/env ruby -wKU

class Named
def initialize(name, child = nil)
@name = name
@child = child
end

def find_by_name(&block)
if block[@name]
self
elsif @child
@child.find_by_name(&block)
end
end

def to_s
@name
end
end

names = %w[one two three].reverse.inject(nil) do |child, name|
Named.new(name, child)
end

puts names.find_by_name { |n| n[0] == ?t }
puts names.find_by_name { |n| n == “four” }

END

Does that make more sense?

Now how do I put this on a class which is an ActiveRecord (i.e. the
find method is already taken)?

find() has an alias called detect(), which I don’t believe
ActiveRecord hides with a method of its own.

BTW Saw your talk at the LSRC. I was very inspired to use Ruby for
everything gluey. :slight_smile:

Glad to hear it!

James Edward G. II

7

On Nov 13, 2007, at 6:01 PM, Mike P. wrote:

You aren’t actually recursing inside the block,
just using the block as a conditional. I was trying to figure out how
to recurse inside the block.

Yeah, I was just using the block inside a recursive method. You are
right.

Can you elaborate on what you mean by “recurse inside a block?” I’m
having trouble thinking of an example.

James Edward G. II

8

On Nov 13, 2007 4:15 PM, James Edward G. II
[email protected] wrote:

having trouble thinking of an example.

James Edward G. II

I think he means something like this?

fact = lambda {|val| return 1 if val <= 0; val * fact[val - 1] }
fact[4] => 24

but I’m not sure…

Pat

9

On Nov 13, 2007, at 8:54 PM, Raul P. wrote:

Trees to each other. A small touch to the << method does it:
end
Yeah, that’s much better. I actually used a structure close to this,
with more niceties of course, for a binary tree I needed. I was
surprised at how easy it was to put together and how flexible it
was. I believe the actual each() method from that one was:

def each(&block)
block[@left] if @left
block[self]
block[@right] if @right
end

James Edward G. II

10

James G. wrote:

Does this give you some ideas?

class Tree
def initialize(name)
@name = name
@leaves = Array.new
end

attr_reader :name

def <<(leaf_name)
@leaves << self.class.new(leaf_name)
self
end
…

I played with this Tree for a while (amazed by its simplicity and
functionality); just a small problem when connecting (and printing)
Trees to each other. A small touch to the << method does it:

def <<(leaf_name)
case leaf_name
when String
@leaves << self.class.new(leaf_name)
when Tree
@leaves << leaf_name
else raise
end
self
end

11

On Nov 13, 2007, at 9:11 PM, James Edward G. II wrote:

 @leaves = Array.new

I played with this Tree for a while (amazed by its simplicity and
end
block[self]
block[@right] if @right
end

Sorry, should have looked it up:

def each(&block)
@left.each(&block) if @left
block[self]
@right.each(&block) if @right
end

James Edward G. II

12

Douglas A. Seifert wrote:

This works:

irb(main):001:0> fact = lambda {|val| val <= 0 ? 1 : val * fact[val-1] }

Another example I coincidentally came up with for another thread,
looking at how the stack is printed on 1.8 and 1.9:

$ ruby -e “a = Proc.new{|d| raise ‘foo’ if d==0; a.call(d-1)};
a.call(20)”
-e:1: foo (RuntimeError)
from -e:1:in call' from -e:1 from -e:1:incall’
from -e:1
from -e:1:in call' from -e:1 from -e:1:incall’
from -e:1
… 30 levels…
from -e:1:in call' from -e:1 from -e:1:incall’
from -e:1

13

Pat M. wrote:

right.

fact = lambda {|val| return 1 if val <= 0; val * fact[val - 1] }
fact[4] => 24

but I’m not sure…

Pat

This works:

irb(main):001:0> fact = lambda {|val| val <= 0 ? 1 : val * fact[val-1] }
=> #Proc:0x00002b8724682be0@:1(irb)
irb(main):002:0> fact.call(4)
=> 24
irb(main):003:0> fact.call(6)
=> 720