How to use `letrec` to define function "length" within the body of function "lengh-it"

Question

(define length-it
  (lambda (ls)
    (length ls 0)))

(define length
  (lambda (ls acc)
    (if (null? ls)
        acc
        (length (cdr ls) (+ acc 1)))))

How to use letrec to put the function length within the body of function length-it?

The output should be (length-it '(1 2 3)) -> 3.

Answer 1

Let's start with what we've got:

(define length-it 
   (lambda (ls) 
      (length ls 0)))

But actually, since there's also a built-in function called length too, let's rename ours to my-length:

(define my-length
  (lambda (ls acc)
    (if (null? ls)
        acc
        (my-length (cdr ls) (+ acc 1)))))

and now,

(define length-it 
   (lambda (ls) 
      (my-length ls 0)))
=
(define length-it 
   (let ((init 0))
     (lambda (ls) 
        (my-length ls 0))))       ;; (0)
=
(define length-it 
   (let ((init 0))                ;; (1)
     (lambda (ls) 
        (my-length ls init))))    ;; (2)

Does this work? To what entity does init(2) refer? Is it init(1)?

Next,

=
(define length-it 
   (let ((init 0)                                      ;; (0)
         (my-length                                    ;; (1)
            (lambda (ls acc) 
               (if (null? ls) 
                   acc 
                   (my-length (cdr ls) (+ acc 1))))))  ;; (2)
     (lambda (ls) 
        (my-length ls init))))                         ;; (3)

Now does this work? (be sure to test this in a new, fresh environment, without my-length being defined separately there at all).

No? Why not?

To what entity does the name init(3) refer? To what does my-length(3) refer? To what does the name my-length(2) refer? Would it work if my-length(2) were referring to my-length(1) as does my-length(3)? Since it doesn't work, my-length(2) must refer to some other my-length defined above the let but do we have any more of them anywhere there?

So can you make it work? Were you supposed to use let there, or that other primitive, letrec? Are the two exactly the same? Probably not, otherwise why would they name the same thing twice? So can we try using the other one there? Would it perhaps make my-length(2) indeed refer to my-length(1) as it was supposed to do?

Does it work now?