Talk:Y combinator: Difference between revisions

Line 43:

A quick glance over the different implementations shows that most of them define the Z combinator. But that is the closest you can get in applicative-order languages. The Z combinator is just one eta-conversion away from the Y combinator. So in lambda calculus these are basically the same: "two functions are the same if and only if they give the same result for all arguments". [[Special:Contributions/131.155.116.18|131.155.116.18]] 17:28, 30 November 2009 (UTC)

=== Ruby has not the Y combinator ===

The current solution for [[Ruby]] is not a Y combinator.

<lang ruby># This is not the Y combinator,

# but it is a stateless fixed-point combinator,

# which is the same function as a Y combinator.

Y = lambda do |f|

lambda {|g| g[g]}[lambda do |g|

f[lambda {|*args| g[g][*args]}]

end]

end</lang>

If it was a Y combinator, it would not work.

<lang ruby># This is the Y combinator,

# but it does not work in Ruby.

# (Almost, the real Y combinator would

# start with f[g[g]] instead of g[g].)

Y = lambda do |f|

lambda {|g| g[g]}[lambda do |g|

f[g[g]] # This is an infinite recursion.

end]

end</lang>

Ruby has '''eager evaluation''', so f[g[g]] will evaluate g[g] before calling f. However, g[g] will evaluate f[g[g]] again, which will evaluate g[g] again. This is an infinite recursion, and the program will crash, by overflowing the call stack, without ever calling f.

But I can also do '''lazy evaluation''' in Ruby. I only need an extra <tt>lambda{g[g]}</tt> to delay the evaluation.

<lang ruby># This is a Y combinator that works in Ruby.

Y = lambda do |f|

lambda {|g| g[g]}[lambda do |g|

f[lambda {g[g]}]

end]

end

# This is factorial.

Fac = Y[lambda {|f| lambda {|n| n < 2 ? 1 : n * f[][n - 1]}}]

# extra brackets ^^ evaluate g[g]</lang>

The extra lambda requires an extra brackets. This is why my factorial function has <tt>f[][n - 1]</tt> and not <tt>f[n - 1]</tt>. The first [] evaluates g[g] (which returns the recursive factorial function), and the second [n - 1] calls the recursive factorial function.

However, I would prefer to write <tt>f[n - 1]</tt> without the extra brackets. The current solution uses <tt>lambda {|*args| g[g][*args]}</tt> to both evaluate g[g] (which returns the recursive function), and to evaluate the recursive function with *args.

<lang ruby># This is not the Y combinator,

# but it is a stateless fixed-point combinator,

# which is the same function as a Y combinator.

Y = lambda do |f|

lambda {|g| g[g]}[lambda do |g|

f[lambda {|*args| g[g][*args]}]

end]

end

# This is factorial.

Fac = Y[lambda {|f| lambda {|n| n < 2 ? 1 : n * f[n - 1]}}]

# no extra brackets! ^^</lang>

This is not the Y combinator, but it is almost the Y combinator. --[[User:Kernigh|Kernigh]] 03:34, 11 April 2011 (UTC)

==Could We remove the recursive examples!==