Recursion with blocks

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?

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

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

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

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.

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

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

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

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

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

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

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

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