[FIXED] How to make recursion using only lambdas in Racket?

Issue

I need some help trying to figure out how to make the code below recursive using only lambdas.

(define (mklist2 bind pure args)
  (define (helper bnd pr ttl lst)
    (cond [(empty? lst) (pure ttl)]
          [else (define (func t) (helper bnd pr (append ttl (list t)) (rest lst)))
           (bind (first lst) func)])
    )
  (helper bind pure empty args))

Solution

Given a sample factorial program -

(define fact
  (lambda (n)
    (if (= n 0)
        1
        (* n (fact (- n 1)))))) ;; goal: remove reference to `fact`

(print (fact 7)) ; 5040

Above fact is (lambda (n) ...) and when we call fact we are asking for this lambda so we can reapply it with new arguments. lambda are nameless and if we cannot use top-level define bindings, the only way to bind a variable is using a lambda's parameter. Imagine something like -

(lambda (r)
  ; ...lambda body...
  ; call (r ...) to recur this lambda
)

We just need something to make our (lambda (r) ...) behave this way -

(something (lambda (r)
  (print 1)
  (r)))

; 1
; 1
; 1
; ... forever

introducing U

This something is quite close to the U combinator -

(define u
  (lambda (f) (f f)))

(define fact
  (lambda (r)     ;; wrap in (lambda (r) ...)
    (lambda (n)
      (if (= n 0)
          1
          (* n ((r r) (- n 1))))))) ;; replace fact with (r r)

(print ((u fact) 7))

; => 5040

And now that recursion is happening thru use of a parameter, we could effectively remove all define bindings and write it using only lambda -

; ((u fact) 7)
(print (((lambda (f) (f f))  ; u
         (lambda (r)         ; fact
           (lambda (n)
             (if (= n 0)
                 1
                 (* n ((r r) (- n 1)))))))
        7))

; => 5040

Why U when you can Y?

The U-combinator is simple but having to call ((r r) ...) inside the function is cumbersome. It'd be nice if you could call (r ...) to recur directly. This is exactly what the Y-combinator does -

(define y
  (lambda (f)
    (f (lambda (x) ((y f) x))))) ;; pass (y f) to user lambda

(define fact
  (lambda (recur)
    (lambda (n)
      (if (= n 0)
          1
          (* n (recur (- n 1))))))) ;; recur directly

(print ((y fact) 7))

; => 5040

But see how y has a by-name recursive definition? We can use u to remove the by-name reference and recur using a lambda parameter instead. The same as we did above -

(define u
  (lambda (f) (f f)))

(define y
  (lambda (r)      ;; wrap in (lambda (r) ...)
    (lambda (f)
      (f (lambda (x) (((r r) f) x)))))) ;; replace y with (r r)

(define fact
  (lambda (recur)
    (lambda (n)
      (if (= n 0)
          1
          (* n (recur (- n 1)))))))

(print (((u y) fact) 7)) ;; replace y with (u y)

; => 5040

We can write it now using only lambda -

; (((u y) fact) 7)
(print ((((lambda (f) (f f))   ; u
          (lambda (r)          ; y
            (lambda (f)
              (f (lambda (x) (((r r) f) x))))))
         (lambda (recur)       ; fact
           (lambda (n)
             (if (= n 0)
                 1
                 (* n (recur (- n 1)))))))
        7))

; => 5040

need more parameters?

By using currying, we can expand our functions to support more parameters, if needed -

(define range
  (lambda (r)
    (lambda (start)
      (lambda (end)
        (if (> start end)
            null
            (cons start ((r (add1 start)) end)))))))

(define map
  (lambda (r)
    (lambda (f)
      (lambda (l)
        (if (null? l)
            null
            (cons (f (car l))
                  ((r f) (cdr l))))))))

(define nums
  ((((u y) range) 3) 9))

(define squares
  ((((u y) map) (lambda (x) (* x x))) nums))

(print squares)
; '(9 16 25 36 49 64 81)

And as a single lambda expression -

; ((((u y) map) (lambda (x) (* x x))) ((((u y) range) 3) 9))
(print (((((lambda (f) (f f)) ; u
           (lambda (r)        ; y
             (lambda (f)
               (f (lambda (x) (((r r) f) x))))))
          (lambda (r)         ; map
            (lambda (f)
              (lambda (l)
                (if (null? l)
                    null
                    (cons (f (car l))
                          ((r f) (cdr l))))))))
         (lambda (x) (* x x))) ; square
        (((((lambda (f) (f f)) ; u
            (lambda (r)        ; y
              (lambda (f)
                (f (lambda (x) (((r r) f) x))))))
           (lambda (r)         ; range
             (lambda (start)
               (lambda (end)
                 (if (> start end)
                     null
                     (cons start ((r (add1 start)) end)))))))
          3)   ; start
         9)))  ; end

; => '(9 16 25 36 49 64 81)

lazY

Check out these cool implementations of y using lazy

#lang lazy

(define y
  (lambda (f)
    (f (y f))))

#lang lazy

(define y
  ((lambda (f) (f f)) ; u
   (lambda (r)
     (lambda (f)
       (f ((r r) f))))))

#lang lazy

(define y
  ((lambda (r)
    (lambda (f)
      (f ((r r) f))))
  (lambda (r)
    (lambda (f)
      (f ((r r) f))))))

Answered By - Mulan

Answer Checked By - Cary Denson (PHPFixing Admin)