recursion with blocks

[Mike Perham]

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?

 

[Jason Roelofs]

Note: parts of this message were removed by the gateway to make it a legal Usenet post.

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?

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

 

[James Edward Gray II]

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 Gray II

 

[Mike Perham]

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.

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 Gray II

 

[James Edward Gray II]

Sort of.

We'll get there=85

I'm still unclear how the actual node is propagated back up as
the result of the find call due to the name =3D=3D "right" block = returning
true.

We're calling a block recursively, just as we would a method. The =20
typical trick for getting a result from that is just to hand a return =20=

value back up the call stack. For example:

#!/usr/bin/env ruby -wKU

class Named
def initialize(name, child =3D nil)
@name =3D name
@child =3D 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 =3D %w[one two three].reverse.inject(nil) do |child, name|
Named.new(name, child)
end

puts names.find_by_name { |n| n[0] =3D=3D ?t }
puts names.find_by_name { |n| n =3D=3D "four" }

__END__

Does that make more sense?

Now how do I put this on a class which is an ActiveRecord (i.e. the =20=

find method is already taken)?

find() has an alias called detect(), which I don't believe =20
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.

Glad to hear it!

James Edward Gray II

 

[Mike Perham]

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.

 

[James Edward Gray II]

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 Gray II

 

[Pat Maddox]

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 Gray 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

 

[Raul Parolari]

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

 

[James Edward Gray II]

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

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 Gray II

 

[James Edward Gray II]

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

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

Sorry, should have looked it up:

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

James Edward Gray II

 

[Douglas A. Seifert]

Note: parts of this message were removed by the gateway to make it a legal Usenet post.

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 Gray 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

This works:

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

 

[Alex Young]

On Nov 13, 2007, at 6:01 PM, Mike Perham 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 Gray 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

This works:

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

<snip>

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:in `call'
from -e:1
from -e:1:in `call'
from -e:1
from -e:1:in `call'
from -e:1
... 30 levels...
from -e:1:in `call'
from -e:1
from -e:1:in `call'
from -e:1