recursion - 在 Racket 中构建内置过程 "build-list"

Question

我正在尝试构建内置程序 build-list在 Racket 中。

内置函数是这样工作的:

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

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

我的实现是递归过程的递归定义:

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

当我调用我的实现时，我有:

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

如您所见，我得到了相同的结果，但顺序相反。

我怎样才能使结果与 native 函数的顺序相同？

P.S.:我已经使用递归定义完成了一个完美运行的迭代过程的实现。我现在正在努力使用完全递归过程生成相同的结果。我已经知道如何用长尾递归解决这个疑问。

这是我的长尾递归实现:

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

Answer 1

好的，所以您正在寻找不使用状态变量和尾调用的答案。您需要一个递归过程，该过程也会演化出一个递归过程。不确定为什么你想要这个除了看看定义会有什么不同。您还应该阅读尾部递归模 cons(here 和 on wikipedia)——它与这个问题相关。

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

注意 aux 调用如何不再处于尾部位置——即 cons 无法完成评估，直到它评估了 aux 调用它的论点。这个过程看起来像这样，在堆栈上进化:

(cons (f 0) <b>...</b>)
(cons (f 0) <b>(cons (f 1) ...)</b>)
(cons (f 0) (cons (f 1) <b>(cons (f 2) ...)</b>))
(cons (f 0) (cons (f 1) (cons (f 2) <b>(cons (f 3) ...)</b>)))
(cons (f 0) (cons (f 1) (cons (f 2) (cons (f 3) <b>(cons (f 4) ...)</b>))))
(cons (f 0) (cons (f 1) (cons (f 2) (cons (f 3) (cons (f 4) <b>empty</b>)))))
(cons (f 0) (cons (f 1) (cons (f 2) (cons (f 3) <b>(cons (f 4) </b>'()<b>)</b>))))
(cons (f 0) (cons (f 1) (cons (f 2) <b>(cons (f 3) </b>'(16)<b>)</b>)))
(cons (f 0) (cons (f 1) <b>(cons (f 2) </b>'(9 16)<b>)</b>))
(cons (f 0) <b>(cons (f 1) </b>'(4 9 16)<b>)</b>)
<b>(cons (f 0) </b>'(1 4 9 16)<b>)</b>
'(0 1 4 9 16)

您会看到 cons 调用保持打开状态，直到 ... 被填充。最后一个 ...在 m 等于 n 之前，不会用 empty 填充。

---

如果您不喜欢内部的 aux 过程，您可以使用默认参数，但这确实会将一些私有(private) API 泄​​露给公共(public) API。也许它对您有用和/或也许您并不真正关心。

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

;; 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) <b>3</b>)
;; => '(9 16)

---

堆栈安全实现

为什么你特别想要一个递归过程(一个增加堆栈的过程)很奇怪，imo，特别是考虑到编写一个堆栈安全的 build-list 过程是多么容易不要增加堆栈。这是一些具有线性迭代过程的递归过程。

第一个非常简单，但使用 acc 参数确实泄漏了一点私有(private) API。您可以使用 aux 过程轻松解决此问题，就像我们在第一个解决方案中所做的那样。

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

查看进化过程

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

这要好得多，因为它可以不断重复使用一个堆栈帧，直到构建整个列表为止。作为一个额外的优势，我们不需要保留从 0 到 n 的计数器。相反，我们反向构建列表并从 n-1 计数到 0。

---

最后，这是另一个演化出线性迭代过程的递归过程。它使用了一个 named-let 和 continuation 传递风格。这次循环有助于防止 API 泄​​漏。

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

如果您使用 compose 和 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)

从这个过程演变而来的过程略有不同，但您会注意到它也不会增加堆栈，而是在堆上创建一系列嵌套的 lambda。所以这对于足够大的 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)