If I have a recursive function like this:

(define (double-n-times x n)
  (if (= n 0)
      x
      (double-n-times (* 2 x) (- n 1))))

How can I make a lambda version of it and never give it a name? ... like if i want to inline it somewhere. Is that possible? (I mean in this case I could use fold - so maybe the example isn't that great) - Is there some kind of symbol or placeholder for "self" that I haven't been able to find? Or do you just have to give it a name.

CodePudding user response：

The Y-Combinator in Racket is:

(lambda (f)
    ((lambda (h) (h h))
     (lambda (g) (f (lambda args (apply (g g) args))))))

This function can take any anonymous function and apply it on themselves recursively.

Let us define your function's part. double-n-times-part written only with lambdas:

(lambda (f)
    (lambda (x n)
      (if (= n 0) x (f (* 2 x) (- n 1))))))

where f we could name as we want - so we could also call it double-n-part.

If we apply the Y-Combinator on this, we get:

((lambda (f)
    ((lambda (h) (h h))
     (lambda (g) (f (lambda args (apply (g g) args))))))
  (lambda (f)
    (lambda (x n)
      (if (= n 0) x (f (* 2 x) (- n 1))))))

This spits out a function which takes the arguments x and n and applies the inner function of the second definiton on them.

So now, without any named functions - only using lambda expressions - you can apply on your arguments - let's say x=3 and n=4:

(((lambda (f)
    ((lambda (h) (h h))
     (lambda (g) (f (lambda args (apply (g g) args))))))
  (lambda (f)
    (lambda (x n)
      (if (= n 0) x (f (* 2 x) (- n 1))))))
 3 4)
;;=> 48 ; as expected (3 * 2 * 2 * 2 * 2)

This is more convenient to read. But we could also define the Y combinator without apply and args when we allow only monadic functions (functions with one arguments) instead of variadic ones. Then it looks like this (and we have to give the arguments one after another like this):

((((lambda (f)
      ((lambda (h) (h h))
        (lambda (g) (f (lambda (x) ((g g) x))))))
    (lambda (f)
      (lambda (x)
        (lambda (n)
          (if (= n 0) x ((f (* 2 x)) (- n 1)))))))
 3) 4)
;;=> 48

CodePudding user response：

The answer to your question is yes, by using macros. But before I talk about that, I have to ask this first: do you ask because you are just curious? Or do you ask because there are some issues, like you don't want to pollute the namespace with names?

If you don't want to pollute the namespace with names, you can simply use local constructs like named let, letrec, or even Y combinator. Alternatively, you can wrap define inside (let () ...).

(let ()
  (define (double-n-times x n)
    (if (= n 0)
        x
        (double-n-times (* 2 x) (- n 1))))
  (double-n-times 10 10))

;; double-n-times is not in scope here

For the actual answer: here's a macro rlam that is similar to lambda, but it allows you to use self to refer to itself:

#lang racket

(require syntax/parse/define)

(define-syntax-parse-rule (rlam args body ... )
  #:with self (datum->syntax this-syntax 'self)
  (letrec ([self (λ args body ...)])
    self))

;; compute factorial of 10
((rlam (x)
   (if (= 0 x)
       1
       (* x (self (sub1 x))))) 10) ;=> 3628800

CodePudding user response：

Yes. Being a placeholder for a name is what lambda function's parameters are there for:

(define (double-n-times x n)
  (if (= n 0)
      x
      (double-n-times (* 2 x) (- n 1))))
=
(define double-n-times (lambda (x n)
  (if (= n 0)
      x
      (double-n-times (* 2 x) (- n 1)))))
=
(define double-n-times (lambda (self)   ;; received here
                         (lambda (x n)
  (if (= n 0)
      x
      (self (* 2 x) (- n 1))))))       ;; and used, here

but what is this "self" parameter? It is the lambda function itself :

= ;; this one's in error:
(define double-n-times ((lambda (u)   ;; call self with self
                          (u u))   ;; to receive self as an argument
                  (lambda (self)
                    (lambda (x n)
  (if (= n 0)
      x
      (self (* 2 x) (- n 1)))))))
  ;; can you see where and why?

= ;; this one isn't:
(define double-n-times ((lambda (u) (u u))
                  (lambda (self)
                    (lambda (x n)
  (if (= n 0)
      x
      ((self self) (* 2 x) (- n 1)))))))

 ;; need to call self with self to actually get that 
 ;; (lambda (x n) ... ) thing to be applied to the values!

And now it works: (double-n-times 1.5 2) returns 6.0.