Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Anonymous recursive blocks?
Author Message
richcash

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

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

Cervantes

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

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

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

Thanks guys, those are some interesting links!

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

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

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

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

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

Cervantes

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

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

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

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

You did it! 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
Cervantes

Posted: 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.
rizzix

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

 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
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 14 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: