Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Anonymous recursive blocks?
Index -> Programming, Ruby -> Ruby Help
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
richcash




PostPosted: Fri May 04, 2007 11:58 pm   Post subject: Anonymous recursive blocks?

Here's a very simple question, but I actually haven't been able to find an answer. Confused

Suppose I have a method that accepts a block parameter, how can I pass a recursive anonymous block to this method. For example a block that computes a factorial?

How can I do this in ruby?

Javascript:
function addTwo (x, fcn) {
        return fcn(x) + 2
}
document.write(addTwo(5, function (x) {return x == 0 ? 1 : x * arguments.callee(x-1)}))
Sponsor
Sponsor
Sponsor
sponsor
Cervantes




PostPosted: Sat May 05, 2007 1:08 pm   Post subject: RE:Anonymous recursive blocks?

If you want a recursive anonymous function, you have to use something called the "Y-combinator". We learned about it in the supplementary lectures in first year CS at Waterloo (the scheme course, not the Java course), but it was still really complicated and I didn't really get it at the time.

this page looks like it should do a pretty good job at explaining it.

That's how it's done with lambda calculus. Perhaps Ruby has something built in to make this easier, but I don't know it.
rdrake




PostPosted: Sat May 05, 2007 5:56 pm   Post subject: RE:Anonymous recursive blocks?

You may find this of some interest, possibly this too.

Stabbing in the dark here, but you may wish to look up the inject method too. I've seen some pretty neat things done with it.
richcash




PostPosted: Sun May 06, 2007 12:37 am   Post subject: Re: Anonymous recursive blocks?

Thanks guys, those are some interesting links! Smile

They might be a bit beyond my functional programming skills, so I'll wait to see if anyone can think of anything else before I try to understand all of that complicated stuff for such a simple task.
richcash




PostPosted: Wed May 09, 2007 11:51 am   Post subject: Re: Anonymous recursive blocks?

I don't think the Y combinator is what I'm looking for. I don't really want to create a recursive lambda, I want to create a recursive block.
code:
def addTwo(n, &block)
        block[n] + 2
end

puts addTwo(5) {|x| x ** 2}

How can I replace the x^2 block with a recursive block? And I still want to allow regular blocks (such as x^2) to be passed to the same method. Can I somehow use the Y combinator to accomplish this?
wtd




PostPosted: Wed May 09, 2007 12:36 pm   Post subject: RE:Anonymous recursive blocks?

I don't think what you're trying to do can or under any imaginable scenario should be done.
Cervantes




PostPosted: Wed May 09, 2007 6:55 pm   Post subject: RE:Anonymous recursive blocks?

wtd is probably right. However, it is a very interesting question--one worth exploring.

richcash, you say you want a recursive block, not a recursive lambda. They are essentially the same thing. The syntax is a little different, but that's it. Look:
Ruby:

def foo(n, &block)
  n + block[n]
end
foo(6) {|x| x ** 2}

def bar(n, f)
  n + f[n]
end
bar(6, lambda {|x| x ** 2})

They do the exact same thing. It's just a different way of writing it.

I'm pretty sure the Y-combinator is what you're looking for.

Do you have any knowledge of functional languages? If so, it might be more useful to try learning this in that language first, where it is more common.
richcash




PostPosted: Wed May 09, 2007 7:22 pm   Post subject: Re: Anonymous recursive blocks?

Thanks for the replies.

Yeah, I actually realized that exact thing a few days ago. Then I did some reading and discovered that blocks are actually converted to Proc objects under the covers after they are passed to the '&'.

But blocks are an integral part of the language. What if I wanted to use an already existing iterator and pass it a recursive block? I don't think it's so impractical or unnecessary to add together all the factorials of an existing array using inject or each

code:
arr = [2, 3, 2, 4, 2, 3, 2, 4]

puts arr.inject(0) {|tot, x| tot + x**2}


What if we had to add together all of the factorials of arr instead of its squares? Would it really be worth redefining the inject method so that it takes a Proc object rather than a block?

Maybe I'm just not thinking about it the right way. Any help is appreciated.
Sponsor
Sponsor
Sponsor
sponsor
Cervantes




PostPosted: Wed May 09, 2007 11:17 pm   Post subject: RE:Anonymous recursive blocks?

Well, to get the sum of the factorials, I think there's a better method. I don't think we should do a simple factorial function on each number, because that will do the lower multiplications (2 * 3 * 4 ... ) a lot of times, which is unnecessary. Instead, I would suggest storing a variable n initialized to 1, and start at the front and passing over the array, modifying the contents of each element to be that element times n, UNLESS n is bigger than that element, in which case add it to the sum and remove it from the array.

This would use a whole lot more memory work, but far less CPU work. It's a tradeoff, I guess.

However, this isn't supposed to be the discussion. Let's say that you want to do the factorial thing your way (the easy way, to boot!). Were you able to get the Y-combinator working with lambda syntax? If so, is it just a syntactic problem with getting the block to work? You can still use the keyword lambda in your blocks, remember.
richcash




PostPosted: Thu May 10, 2007 1:38 pm   Post subject: Re: Anonymous recursive blocks?

Hey, that's a cool way to do the factorials, Cervantes. I'll have to try it sometime.


Cervantes wrote:
Were you able to get the Y-combinator working with lambda syntax

Yes, although I didn't understand all of it.
Ruby:
def addTwo (n, f)
        f.call(n) + 2
end
puts addTwo(5, lambda { |le|
  lambda { |f| f.call(f) }.call( lambda { |f|
           le.call(lambda { |x| f.call(f).call(x) }) })
}.call(lambda { |recurse|
  lambda { |n|
    if n == 0 then
      1
    else
      n * recurse.call(n-1)
    end
  }
}) )        #=> outputs 122


Cervantes wrote:
You can still use the keyword lambda in your blocks, remember.

Oh yeah, I didn't realize that. But it's still hard to do in the above. If you make the whole thing into a block, then you have to pass the 'n' from the addTwo method to the new block. Then I have to pass this value to one of the lambdas, which I don't know if I can do. Does anyone know how to do this?

The other way would be to turn the first lambda into a block, but blocks can not be called until they are passed to the method, so that wouldn't work either.

Does anyone know how I can use the Y-combinator in a block?
Cervantes




PostPosted: Thu May 10, 2007 10:08 pm   Post subject: RE:Anonymous recursive blocks?

Woo, I got it! It became pretty easy once I fixed up the indenting.

All you do is take the lambda version, and move it outside, so it's a block. You get rid of the lambda keyword at the front, because that's not necessary any more. Now the thing is our block has to consume a number, so I made that parameter be called "p". It then returns a lambda function that does all the stuff your lambda function did, and then I called that lambda function at p.

Ruby:

def addTwo (n, &f)
  f[n] + 2
end
puts addTwo(5) {|p|
  (lambda {|le|
    lambda {|f|
      f.call(f)
    }.call(lambda {|f|
             le.call(lambda {|x| f.call(f).call(x)})
    })
  }.call(lambda {|recurse|
  lambda {|n|
    if n == 0 then
      1
    else
      n * recurse.call(n-1)
    end
  }
})).call(p)}        #=> outputs 122
richcash




PostPosted: Thu May 10, 2007 11:36 pm   Post subject: Re: Anonymous recursive blocks?

Surprised You did it! Very Happy Thanks so much, this is great! I knew that would be possible I just couldn't come up with it.

I've learned a lot from a simple question. I think I'm glad there was no arguments.callee equivalent in Ruby Laughing
Cervantes




PostPosted: Fri May 11, 2007 6:28 pm   Post subject: RE:Anonymous recursive blocks?

Haha, yeah. Good perspective. This is a pretty natural question to ask, but the solution is by no means simple. Smile
rizzix




PostPosted: Mon Jun 25, 2007 2:22 pm   Post subject: RE:Anonymous recursive blocks?

y-combinator in haskell:

Haskell:
y f = f (y f)

Using it...
Haskell:
take 10 $ y (\f -> 1:1:(zipWith (+) f $ tail f))


It is the coolest language in the world for a reason Wink
Display posts from previous:   
   Index -> Programming, Ruby -> Ruby Help
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 14 Posts ]
Jump to:   


Style:  
Search: