Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon.

Pages: 1-

Why does α-reduction occur?

Name: Anonymous 2008-02-10 16:09

I don't see the need for α-reduction in this instance:

Y g = (λf . (λx . f (x x)) (λx . f (x x))) g
Y g = (λx . g (x x)) (λx . g (x x))              (β-reduction of λf - applied main function to g)
Y g = (λy . g (y y)) (λx . g (x x))              (α-conversion - renamed bound variable)
Y g = g ((λx . g (x x)) (λx . g (x x)))          (β-reduction of λy - applied left function to right function)
Y g = g (Y g)                                    (definition of Y)

Source: http://en.wikipedia.org/wiki/Y_combinator

Name: gdsafad 2008-02-10 16:10

gfadgad

Name: Anonymous 2008-02-10 16:32

(define (foldr f z xs)
  (if (null? xs)
      z
      (f (car xs) (foldr f z (cdr xs)))))

Make this function tail recursive.

Name: Anonymous 2008-02-10 17:09

(define (foldr. f z xs)
  (let iter ((xs xs) (z z))
    (if (pair? xs)
        (iter (cdr xs) (f (car xs) z))
        z)))

Name: Anonymous 2008-02-10 17:10

Now can you please tell me why α-conversion is done in the above example?

Name: Anonymous 2008-02-10 17:12

Also, it's a procedure, not a function.

Name: Anonymous 2008-02-10 17:30

[b][u]Fuck you, [i]/prog/[i].[/u][/b]

Name: Anonymous 2008-02-10 17:31

I'll try again, and this time I really mean it:


    Fuck you, /prog/.

Name: Anonymous 2008-02-10 17:41

I love it when a plan comes together.

Name: Anonymous 2008-02-10 17:44

>>5
Why do you think it is not needed?

Name: Anonymous 2008-02-10 17:58

>>10
You get the same result without it.

Name: Anonymous 2008-02-10 18:02

Compare

Y g = (λx . g (x x)) (λx . g (x x))
Y g = (λy . g (y y)) (λx . g (x x))
Y g = g ((λx . g (x x)) (λx . g (x x)))

to

Y g = (λx . g (x x)) (λx . g (x x))
Y g = g ((λx . g (x x)) (λx . g (x x)))

β-reduction without the α-conversion gives the same result.

Name: Anonymous 2008-02-10 18:12

α-conversion exists to stop free-variable capture in β-reduction. In (λx.λy.y x) (λz.y), α-conversion is necessary to change the ys to some other symbol, so as not to conflict with the free-variable in (λz.y) which would cause the wrong output, λy.y (λz.y). A correct output is λk.k (λz.y), or even λz.z (λz.y).

Name: Anonymous 2008-02-10 18:17

α-conversion exists to QUEER stop free-variable capture in β-reduction. In (λx.λy.y x) (λz.y), α-conversion is necessary to change the ys to some QUIM other symbol, so CUM as not to conflict with the free-variable TOSSER in (λz.y) which would cause THE SODDING wrong OUTPUT, λy.y CHOCOLATE (λz.y). A correct NIGGER output is λk.k (λZ.Y), or even λz.z (λz.y).

Name: Anonymous 2008-02-11 6:28

You disappoint me, /prog/.

Name: Anonymous 2008-02-11 7:57

>>15
That's what she said.

Name: Anonymous 2008-02-11 8:25

In this case you don't need it, but in general you need α-conversion to avoid capturing free variables.
In this case it is probably done to avoid ambiguity, when referring to the β-reduction of λy.

Name: Anonymous 2009-03-06 8:12


The lines of if   the current part   of a string   is a list   why does this   statement come out   and something went   wrong with reading   or closing the   if As you   know what it   does The answer   my friend is   blowing in the   IT field but   is otherwise social.

Name: Anonymous 2009-03-06 9:45


The board to sign   up with Aircell   Aircell offers an.

Name: Anonymous 2009-03-06 15:22

com/digamitus.

Name: Anonymous 2013-03-18 18:53

>>1
Somewhere around this area. *spreads asscheeks*

Name: Anonymous 2013-03-18 19:30

>>13
thank you
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -