Building the built-in procedure "build-list" in Racket

Question

I am trying to build the built-in procedure build-list in Racket.

The built-in function works like this:

(build-list 10 (lambda (x) (* x x)))

>> '(0 1 4 9 16 25 36 49 64 81)

My implementation is a recursive definition for a recursive procedure:

(define (my-build-list-recur list-len proc)
  (if (= list-len 0)
      '()
      (cons  (proc (sub1 list-len)) (my-build-list-recur (sub1 list-len) proc))))

When I call my implementation, I have:

(my-build-list-recur 10 (lambda (x) (* x x)))
>> '(81 64 49 36 25 16 9 4 1 0)

As you might have seen, I get the same result, but in a reverse order.

What can I do to have the result in the same order as the native function?

P.S.: I have done an implementation using a recursive definition for an iterative procedure which works perfectly. I am struggling now to generate the same result with the totally recursive procedure. I already know how to solve this doubt with long tail recursion.

This is my implementation with long tail recursion:

(define (my-build-list list-len proc)
  (define (iter list-len accu n)
    (if (= (length accu) list-len)
        (reverse accu)
        (iter list-len (cons (proc n) accu) (add1 n))))
  ;(trace iter)
  (iter list-len '() 0))

Whit

I'd use a helper function that counts from 0 up to list-len - 1. – Pinta

You could simply write a wrapper procedure that calls the recursive procedure, then reverses the result. – Glasper

Check out the way it's implemented in racket's source if you're looking to emulate its behavior – Canadianism

You keep saying "long" tail recursion. What do you think "long" means? How does it differ from (non-long) tail recursion? – Lusitania

@naomik thanks for trying to help me. I am a begginer but I am trying to learn functional programming with the classic SICP book. It is really clear in the book a difference between a recursive definition which generates a recursive procedure and a recursive definition which generates an iterative procedure (the iterative one, with state variables, is also called long tail recursion). I am seeking a way to solve the question above without using long tail recursion. Not sure if I am fully clear here. Maybe, I am misunderstanding some concept. – Whit

This quote shows how important this difference is for the authors of the book: azquotes.com/picture-quotes/… – Whit

Hmm, I'm also reading SICP but I don't remember any distinction between "tail recursion" and "long tail recursion" – I do however remember the recursive process (recursion in non-tail position) vs linear iterative process (recursion in tail position). I'll update my answer accordingly. – Lusitania

Answer 1

Ok so you're looking for an answer that does not use state variables and a tail call. You want for a recursive procedure that also evolves a recursive process. Not sure why you want this other than just to see how the definition would differ. You should also read about tail recursion modulo cons (here, and on wikipedia) – it's relevant to this question.

;; recursive procedure, recursive process
(define (build-list n f)
  (define (aux m)
    (if (equal? m n)
        empty
        (cons (f m) (aux (add1 m)))))
  (aux 0))

(build-list 5 (λ (x) (* x x)))
;; => '(0 1 4 9 16)

Notice how the aux call is no longer in tail position – ie, cons cannot finish evaluating until it has evaluated the aux call in its arguments. The process will look something like this, evolving on the stack:

(cons (f 0) ...)
(cons (f 0) (cons (f 1) ...))
(cons (f 0) (cons (f 1) (cons (f 2) ...)))
(cons (f 0) (cons (f 1) (cons (f 2) (cons (f 3) ...))))
(cons (f 0) (cons (f 1) (cons (f 2) (cons (f 3) (cons (f 4) ...)))))
(cons (f 0) (cons (f 1) (cons (f 2) (cons (f 3) (cons (f 4) empty)))))
(cons (f 0) (cons (f 1) (cons (f 2) (cons (f 3) (cons (f 4) '())))))
(cons (f 0) (cons (f 1) (cons (f 2) (cons (f 3) '(16)))))
(cons (f 0) (cons (f 1) (cons (f 2) '(9 16))))
(cons (f 0) (cons (f 1) '(4 9 16)))
(cons (f 0) '(1 4 9 16))
'(0 1 4 9 16)

You'll see that the cons calls are left hanging open until ... is filled in. And the last ... isn't filled in with empty until m is equal to n.

---

If you don't like the inner aux procedure, you can use a default parameter, but this does leak some of the private API to the public API. Maybe it's useful to you and/or maybe you don't really care.

;; recursive procedure, recursive process
(define (build-list n f (m 0))
  (if (equal? m n)
      '()
      (cons (f m) (build-list n f (add1 m)))))

;; still only apply build-list with 2 arguments
(build-list 5 (lambda (x) (* x x)))
;; => '(0 1 4 9 16)

;; if a user wanted, they could start `m` at a different initial value
;; this is what i mean by "leaked" private API
(build-list 5 (lambda (x) (* x x) 3)
;; => '(9 16)

---

Stack-safe implementations

Why you'd specifically want a recursive process (one which grows the stack) is strange, imo, especially considering how easy it is to write a stack-safe build-list procedure which doesn't grow the stack. Here's some recursive procedures with a linear iterative processes.

The first one is extremely simple but does leak a little bit of private API using the acc parameter. You could easily fix this using an aux procedure like we did in the first solution.

;; recursive procedure, iterative process
(define (build-list n f (acc empty))
  (if (equal? 0 n)
      acc
      (build-list (sub1 n) f (cons (f (sub1 n)) acc))))

(build-list 5 (λ (x) (* x x)))
;; => '(0 1 4 9 16)

Check out the evolved process

(cons (f 4) empty)
(cons (f 3) '(16))
(cons (f 2) '(9 16))
(cons (f 1) '(4 9 16))
(cons (f 0) '(1 4 9 16)) 
;; => '(0 1 4 9 16)

This is insanely better because it can constantly reuse one stack frame until the entire list is built. As an added advantage, we don't need to keep a counter that goes from 0 up to n. Instead, we build the list backwards and count from n-1 to 0.

---

Lastly, here's another recursive procedure that evolves a linear iterative process. It utilizes a named-let and continuation passing style. The loop helps prevent leaking the API this time.

;; recursive procedure, iterative process
(define (build-list n f)
  (let loop ((m 0) (k identity))
    (if (equal? n m)
        (k empty)
        (loop (add1 m) (λ (rest) (k (cons (f m) rest)))))))

(build-list 5 (λ (x) (* x x)))
;; => '(0 1 4 9 16)

It cleans up a little tho if you use compose and curry:

;; recursive procedure, iterative process
(define (build-list n f)
  (let loop ((m 0) (k identity))
    (if (equal? n m)
        (k empty)
        (loop (add1 m) (compose k (curry cons (f m)))))))

(build-list 5 (λ (x) (* x x)))
;; => '(0 1 4 9 16)

The process evolved from this procedure is slightly different, but you'll notice that it also doesn't grow the stack, creating a sequence of nested lambdas on the heap instead. So this would be sufficient for sufficiently large values of n:

(loop 0 identity)                        ; k0
(loop 1 (λ (x) (k0 (cons (f 0) x)))      ; k1
(loop 2 (λ (x) (k1 (cons (f 1) x)))      ; k2
(loop 3 (λ (x) (k2 (cons (f 2) x)))      ; k3
(loop 4 (λ (x) (k3 (cons (f 3) x)))      ; k4
(loop 5 (λ (x) (k4 (cons (f 4) x)))      ; k5
(k5 empty)
(k4 (cons 16 empty))
(k3 (cons 9 '(16)))
(k2 (cons 4 '(9 16)))
(k1 (cons 1 '(4 9 16)))
(k0 (cons 0 '(1 4 9 16)))
(identity '(0 1 4 9 16))
'(0 1 4 9 16)

Lusitania

Ha, hardly. I'm constantly humbled by others answering on the racket tag. I'm still just learning the basics ^_^ – Lusitania

This is a fantastic answer, and the formatting on the codeblock shows really wonderful attention to detail. One small other thing to mention is that Racket does not use the C stack, and its stack can effectively grow unbounded, so you won’t ever have a “stack overflow” error, you’ll just run out of memory. That makes writing things tail recursively somewhat less important depending on the algorithm in question, though it’s still important to think about in certain situations, and it can’t hurt! – Jervis

I've edited in the link to WP article on TRMC, where we can find Scheme function duplicate, cleaned-up with the named let "scheme-fu", as hinted in the blog you linked to. – Sulfonate

@AlexisKing very cool, I did not know a stack overflow was so difficult to "achieve" in racket. Thanks for sharing ^_^ – Lusitania

@WillNess welcomed edit. I had a different source in mind when creating the TRMC link but couldn't seem to find it. I settled with the one that you originally saw. Thanks for cleaning up the eval visualizations too. ありがとう！ – Lusitania