Asp Forum - recursion with blocks

Mike Perham

11/13/2007 9:49:00 PM

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

12 Answers

Jason Roelofs

11/13/2007 9:56:00 PM

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

On Nov 13, 2007 4:49 PM, Mike Perham <mperham@gmail.com> 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-....
>
>
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 Gray

11/13/2007 10:03:00 PM

On Nov 13, 2007, at 3:49 PM, Mike Perham 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 Gray II

Mike Perham

11/13/2007 11:13:00 PM

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. :-)

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

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

James Gray

11/13/2007 11:36:00 PM

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

> 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

11/14/2007 12:01:00 AM

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.
--
Posted via http://www.ruby-....

James Gray

11/14/2007 12:15:00 AM

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

Pat Maddox

11/14/2007 12:21:00 AM

On Nov 13, 2007 4:15 PM, James Edward Gray II <james@grayproductions.net> wrote:
> 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

Raul Raul

11/14/2007 2:54:00 AM

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

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

James Gray

11/14/2007 3:11:00 AM

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

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

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 Gray

11/14/2007 3:16:00 AM

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

> On Nov 13, 2007, at 8:54 PM, Raul Parolari wrote:
>
>> James Gray 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
>
> 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

comp.lang.ruby

recursion with blocks

Mike Perham

Jason Roelofs

James Gray

Mike Perham

James Gray

Mike Perham

James Gray

Pat Maddox

Raul Raul

James Gray

James Gray

x Login to ForumsZone