Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Understanding the Y Combinator

8dcc.github.io

Post reply on HN
Print view View original

71–73 of 73 posts

Re: Understanding the Y Combinator

#71

Post by hollerith »

lacker wrote: post #70
hollerith wrote: post #50

Earlier quoted context omitted.

Here is Haskell code in which the Y combinator (named "fix" in the code) is given the type (a -> a) -> a: https://play.haskell.org/saved/ndm83XBr This next a very simple Haskell program that just prints the first 8 non-negative integers: main = putStrLn $ show $ take 8 $ iterate (+ 1) 0 The linked code is just an elaboration of that where instead of using the built-in "iterate" we define an equivalent "iterate2". Usu…

I would not call that the Y combinator. As traditionally defined the Y combinator is Y = lambda f: (lambda x: f(x(x)))(lambda x: f(x(x))) so it involves applying x to x. So clearly as shown here you can express in Python. The language has to not enforce sane types. But I would say it only makes sense in the untyped lambda calculus because in any other language there would be a more reasonable way to achieve the same…

You can say that "fix" is not the Y combinator, but I've demonstrated in Haskell code that "fix" does the thing the Y combinator is famous for doing: namely, to eliminate the need for recursive calls. (In fact, I repeat the Haskell code in this comment.)

Just because your definition is syntactically different from mine does not mean the definitions are not equivalent.

My guess as to why Python programmers define the Y combinator the way you is that in Python a function's arguments are evaluated eagerly whereas in Haskell they are evaluated lazily with the result that my definition would tend to enter an infinite loop in Python (but even in a language with eager evaluation, I suspect a simpler definition than yours is possible, so I'm not sure what is going on with your definition, which is not surprising since I'm no Python expert).

That is all I will to say in reply to you, but I do want to take this opportunity to fix a problem with my previous comment, namely, the fact that although HN comments tend to persist forever, links to sites other than HN rot fairly quickly: I will now repeat here on HN the tiny Haskell program that in my previously comment I put behind a link. I'll also avoid the unnecessary use of "$", "putStrLn" and "show" to make the code easier to read by Haskell newbies.

Because the convention in Haskell is to reserve single-character variable names for local variables, we name the Y combinator "fix":

  fix :: (a -> a) -> a
  fix f = f (fix f)
Now to demonstrate the use of "fix". My go-to toy Haskell program is this next which prints the first 8 non-negative integers.

  main = print (take 8 (iterate (+1) 0))
Unfortunately that is too much of a toy for our purpose here because I does not contain a recursive call, so we will pretend that the function "iterate" is not pre-defined in Haskell with the result that we would need to define it ourselves (and call it iterate2 because of course the name "iterate" is already taken). All the code in this comment has been tested; all four versions (the one above and the three below) of our toy program produce the same output.

  main = print (take 8 (iterate2 (+1) 0))
  iterate2 :: (a -> a) -> a -> [a]
  iterate2 f x = x : iterate2 f (f x)
The final mention of "iterate2" above is a recursive call. We replace it with a (non-recursive) call to "fix" as follows:

  main = print (take 8 (iterate2 (+1) 0))
  iterate2 :: (a -> a) -> a -> [a]
  iterate2 f = fix (\self -> \x -> x : self (f x))
And here is an intermediate form of our toy program that might help the reader understand how the form that uses "fix" was derived from the original form:

  main = print (take 8 (iterate2 (+1) 0))
  iterate2 :: (a -> a) -> a -> [a]
  iterate2 f = loop where
      loop x = x : loop (f x)

Re: Understanding the Y Combinator

#72

Post by codethief »

tromp wrote: post #47
lacker wrote: post #38

It's a shame that I like Y Combinator the organization so much, because I find the y combinator as a programming concept to be aesthetically displeasing. It only makes sense in the untyped lambda calculus, where types are all conflated and errors are forbidden. It relies on the fact that you can take any x and "apply x to itself". These properties are essentially gimmicks of the untyped lambda calculus. It's like the…

Between lambda calculus and LISP, I find LISP to be the ugly one, not only because of its far greater complexity, but also its lack of referential transparency. David Turner / Ben Lynn make some good observations about LISP in section "History versus myth" of [1]. If lack of types is what you dislike of the plain lambda calculus, then Haskell is a much better solution than LISP. [1] https://crypto.stanford.edu/~blynn…

Wow, this link sent me down a rabbit hole! What a great website! Thanks so much!

Re: Understanding the Y Combinator

#73

Post by codethief »

hollerith wrote: post #40
lacker wrote: post #38

It's a shame that I like Y Combinator the organization so much, because I find the y combinator as a programming concept to be aesthetically displeasing. It only makes sense in the untyped lambda calculus, where types are all conflated and errors are forbidden. It relies on the fact that you can take any x and "apply x to itself". These properties are essentially gimmicks of the untyped lambda calculus. It's like the…

>It only makes sense in the untyped lambda calculus Is that really true? ISTR you can impose the type (A -> A) -> A on the Y combinator.

At least in simply-typed lambda calculus it's not possible, see also https://crypto.stanford.edu/~blynn/lambda/simply.html :

> This implies the Y combinator and omega combinator cannot be expressed in this system. […] In other words, programs always halt.

I assume the reason you can still write down the type in Haskell (as in your example further down) is that Haskell types include the bottom?

Post reply on HN