Recursion with blocks

ruby-talk
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?

···

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

2

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 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-forum.com/\.

3

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

···

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?

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 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-forum.com/\.

5

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-forum.com/\.

6

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

···

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

7

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

···

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

8

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-forum.com/.

9

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

···

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

10

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

···

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.

11

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

12

Pat Maddox 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] }
=> #<Proc:0x00002b8724682be0@(irb):1>
irb(main):002:0> fact.call(4)
=> 24
irb(main):003:0> fact.call(6)
=> 720

···

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:

13

Douglas A. Seifert wrote:

Pat Maddox 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

···

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:

--
Alex