Y Combinator in Scheme using Define

Question

In order to learn what a fixed-point combinator is and is used for, I wrote my own. But instead of writing it with strictly anonymous functions, like Wikipedia's example, I just used define:

(define combine (lambda (functional)
                  (functional (lambda args (apply (combine functional) args))))

I've tested this with functionals for factorial and fibonacci, and it seems to work. Does this meet the formal definition of a fixed-point combinator?

Exercise 2: Y combinator without using define or letrec :) — leppie
– leppie, Commented Jan 14, 2011 at 6:13

AlcubierreDrive · Accepted Answer · 2011-05-18 08:38:44Z

5

EDIT: While chessweb or anyone else corroborates his answer, temporarily consider his answer correct and this one wrong.

It seems the answer is yes. Apparently the exact same combinator appears here, midway down the page:

(define Y
    (lambda (f)
      (f (lambda (x) ((Y f) x)))))

edited May 18, 2011 at 8:38

answered Jan 14, 2011 at 1:41

AlcubierreDrive

3,6642 gold badges32 silver badges45 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Yasir Arsanukayev Over a year ago

You shouldn't. You're encouraged to answer you own questions. IIRC you can accept your own answer in 2 days after you gave it.

Eli Barzilay Over a year ago

The main point of teaching the Y combinator is to see how you can implement recursion with just functions. By writing a recursive definition, you fail to do that -- so you end up with something that works, but it's only useful in understanding what Y is supposed to do. Mike's text would be a good place to read about it in depth and see how the define-less version is derived.

chessweb · Accepted Answer · 2011-05-17 19:13:31Z

3

The answer is no, because according to the blog referred to in the previous answer, it doesn't even meet the definition of combinator, since 'combine' is a free variable.

edited May 17, 2011 at 19:13

answered May 17, 2011 at 18:34

chessweb

4,6935 gold badges30 silver badges33 bronze badges

1 Comment

AlcubierreDrive Over a year ago

Thanks for pointing that out. Just to be sure that the blog's definition is correct, do you consider it equivalent to Wikipedia's definition: "A combinator is a higher-order function that uses only function application and earlier defined combinators to define a result from its arguments."? See en.wikipedia.org/wiki/Combinatory_logic

Collectives™ on Stack Overflow

Y Combinator in Scheme using Define

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related