recursionlambdafunctional-programmingschemeracket

How to make recursion using only lambdas in Racket?


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))))))