Talk:Y combinator

Haskell stateless?

I don't know Haskell, but isn't the definition:

 y f = f (y f)

not stateless as it seems to be defining y by referring to y. Haskell, no doubt has lazy evaluation to make it terminate, but the task does ask for a non-recursive, stateless definition of y. --Paddy3118 09:18, 28 February 2009 (UTC)

I googled this. --Paddy3118 09:22, 28 February 2009 (UTC)

It's impossible to write a fixed-point combinator (or perform any recursion, for that matter) in any statically-typed language, without using either recursive functions or recursive types. --Spoon! 10:42, 28 February 2009 (UTC)

Hi Spoon, The task does not rule out recursive types (I didn't know what they were at the time of writing) - just recursive functions. --Paddy3118 11:05, 28 February 2009 (UTC)

It's not immediatly clear what is meant by the term "stateless," but let's assume it means something like "definable System F." (most of Haskell can be viewed as a simple extension of System F). In that case Spoon! is correct; in most flavors of System F, the fixpoint combinator must be a primitive. This follows from the fact that System F (without fix) is strongly normalizing. On the other hand it is not the case that "any recursion" requires the general recursive fixed-point combinator. Primitive recursion can be easily encoded using the Church numerals (which are definable in System F), and covers a variety of interesting recursive definitions.

On the other hand if we add recursive types, they provide a kind of loop-hole that allows us to type the standard fixed-point combinators from untyped lambda calculi; the linked message above demonstrates one way to do this. The addition of mutable state (a la lisp) also allows the definition of fixed point combinators IIRC. I believe (although I am less sure about this) that a call/cc primitive is also sufficent to define fixed point combinators.

At any rate, here is a way to define the Y combinator using recursive types in Haskell that is a little nicer than the one in the message above.

<lang haskell> newtype Mu a = Roll { unroll :: Mu a -> a }

fix :: (a -> a) -> a fix = \f -> (\x -> f (unroll x x)) $ Roll (\x -> f (unroll x x))

fac :: Integer -> Integer fac = fix $ \f n -> if (n <= 0) then 1 else n * f (n-1)

fibs :: [Integer] fibs = fix $ \fbs -> 0 : 1 : fix zipP fbs (tail fbs)

 where zipP f (x:xs) (y:ys) = x+y : f xs ys

main = do

 print $ map fac [1 .. 20]
 print $ take 20 fibs

</lang>

--RWD

Is this really the "Y" combinator?

According to wp:Fixed point combinator, and here page 6, and here page 2, the Y combinator is the precise form λf·(λx·f (x x)) (λx·f (x x)), which does not work for applicative-order evaluation. The version you are using for Python is closely related to what they call the Z combinator, which is λf. (λx. f (λy. x x y)) (λx. f (λy. x x y)) (the version you are using is just one step "before" this; one step of evaluation will produce this). So I am not sure if we should have named the article the "Y" combinator. --71.106.173.110 20:49, 1 March 2009 (UTC)

Hmm, They are related, and my reference, (and others), seem to have lumped them both together under the familiar title "Y combinator". I suggest a redirect of "Z combinator" to this page and a note be added to task. --Paddy3118 05:48, 2 March 2009 (UTC)

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". 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,

1. but it is a stateless fixed-point combinator,
2. 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,

1. but it does not work in Ruby.
2. (Almost, the real Y combinator would
3. 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 lambda{g[g]} 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

1. This is factorial.

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

1. extra brackets ^^ evaluate g[g]</lang>

The extra lambda requires an extra brackets. This is why my factorial function has f[][n - 1] and not f[n - 1]. 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 f[n - 1] without the extra brackets. The current solution uses lambda {|*args| g[g][*args]} 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,

1. but it is a stateless fixed-point combinator,
2. 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

1. This is factorial.

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

1. no extra brackets! ^^</lang>

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

Could We remove the recursive examples!

After all it is disallowed by the task. (Haskell, Ocaml) --Paddy3118 00:19, 28 March 2009 (UTC)

The D example is a good way, I think, of adding content even though it does not perform the task as it:

1. States that it does not do the task up-front
2. Gives inciteful information on why, and how close you can get.

--Paddy3118 05:52, 20 May 2009 (UTC)

I first would analyze why the code author wrote «The usual version» about the recursion one. Maybe it's more natural to Haskell (or functional languages in general)? --ShinTakezou 09:34, 20 May 2009 (UTC)

Hi ShinTakezou, The idea behind the Y combinator is to create recursion without explicit recursion. It is akin to asking for a Bogosort and getting back some other sort. It isn't what the task has asked for.

Just as it would be pointless to actually use Bogosort in the real world, it is missing the point to show a recursive fibonacci generator when a Y-combinator one was asked for. --Paddy3118 20:19, 20 May 2009 (UTC)

Slate entry incomplete?

Thanks for adding another language implementation, but:

"The task is to define the stateless Y combinator and use it to compute factorials and Fibonacci numbers from other stateless functions or lambda expressions."

Unfortunately you haven't defined it, and it seems as if it hasn't been used to compute the two functions. --Paddy3118 05:54, 5 June 2009 (UTC)

Perl 6 comment on the need for Y?

Can anyone explain the comment:

"Note that Perl 6 doesn't actually need a Y combinator because you can name anonymous functions from the inside"

I cannot make sense of it as the Y combinator seems to be a way of adding recursion to mainly theoretical functional languages that don't allow variables holding state. I doubt if any of the RC languages actually need Y so it seems superfluous. --Paddy3118 09:51, 11 September 2010 (UTC)

Well, yes, it's superfluous if you want to use state variables instead, but the point is that the Perl 6 construct allows you to continue to write in a stateless idiom if you so choose, and at least encode tail recursion without state. And if the Y combinator is used for other purposes, well, we can do that too... :-) --TimToady 04:05, 12 September 2010 (UTC)

Ta! --Paddy3118 04:31, 12 September 2010 (UTC)

"Y" combinator in Scheme

Actually, there is a way to implement the Y combinator in Scheme: <lang scheme> (define Y

 (lambda (f)
   ((lambda (x)
      (f (delay (x x))))
    (lambda (x)
      (f (delay (x x)))))))

</lang> but you have to call the function with <lang scheme>(force f)</lang> example: <lang scheme> (define fact

 (Y
  (lambda (f)
    (lambda (n)
      (if (zero? n)
          1
          (* n ((force f) (- n 1))))))))

</lang> Edit: Err... I think I messed it up a little, it should be ok now. Edit2: You can obviously also do <lang scheme> (define fact

 (lambda (f)
   (lambda (n)
     (if (zero? n)
         1
         (* n ((force f) (- n 1)))))))

</lang> and then call it as <lang scheme> > ((Y fact) 5) 120</lang> 93.144.202.116

Is the C++ a combinator or just recursion "macro"?

I was concerned as the definition of Y explicitely depends on Y, which I thought is the kind of thing the Y combinator was trying to dodge! Mind you, my knowledge of this C++ esoteria comes down to reading this. --Paddy3118 06:48, 10 April 2011 (UTC)

Isn't the operator() defined within the const struct : RecursiveFunc calling itself in the line return (s->operator()(f, s))(x); ?

PicoLisp not incorrect

<lang PicoLisp>(de Y (F)

  (let X (curry (F) (Y) (F (curry (Y) @ (pass (Y Y)))))
     (X X) ) )</lang>

Someone marked this incorrect because "Y is explicitly recursive on Y". The (Y) second parameter to curry declares a local function parameter Y which is not the same as the original Y. So the original Y never recurses on itself; it calls a different Y. I removed the {{incorrect}} tag from the PicoLisp example. --Kernigh 18:59, 11 April 2011 (UTC)

Thanks for the explanation Kernigh. I goofed. --Paddy3118 19:57, 11 April 2011 (UTC)

Wolfram example

This example was added to Fixed-point combinator in wikipaedia. It does not belong there, but it could belong here.

A Y-combinator implementation of factorial in the Wolfram Language is,

 Y = Function[f, #[#]&[Function[g, f[g[g][##]&]]]];
 factorial = Y[Function[f, If[# < 1, 1, # f[# - 1]] &]];
 factorial[6] (*Yields 120*)

Thepigdog (talk) 03:18, 26 May 2015 (UTC)