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)

Could We remove the recursive examples!

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