Anonymous recursive blocks?

[richcash]

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]

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]

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]

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]

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]

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

[Cervantes]

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]

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]

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]

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]

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]

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]

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

[rizzix]

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