在 Racket 中构建内置程序 "build-list"
Building the built-in procedure "build-list" in Racket
我正在尝试在 Racket 中构建内置程序 build-list。
内置函数是这样工作的：
(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)
如您所见，我得到了相同的结果，但顺序相反。
我怎样才能使结果与本机函数的顺序相同？
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))
好的，所以您正在寻找不使用状态变量和尾调用的答案。您想要一个递归 过程 ，它也演化出一个递归 过程 。不确定 为什么 你想要这个，除了看看定义会有什么不同。您还应该阅读 tail recursion modulo cons (here, and 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 调用保持打开状态，直到 ... 被填充。最后一个 ... 没有被 empty 填充直到 m 等于 n.
如果您不喜欢内部 aux 过程，您可以使用默认参数，但这确实会将一些私有 API 泄露给 public API.也许它对你有用and/or也许你并不关心。
;; 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 参数确实泄漏了一点私有 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)
我正在尝试在 Racket 中构建内置程序 build-list。
内置函数是这样工作的：
(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)
如您所见，我得到了相同的结果，但顺序相反。
我怎样才能使结果与本机函数的顺序相同？
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))
好的，所以您正在寻找不使用状态变量和尾调用的答案。您想要一个递归 过程 ，它也演化出一个递归 过程 。不确定 为什么 你想要这个，除了看看定义会有什么不同。您还应该阅读 tail recursion modulo cons (here, and 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 调用保持打开状态，直到 ... 被填充。最后一个 ... 没有被 empty 填充直到 m 等于 n.
如果您不喜欢内部 aux 过程，您可以使用默认参数，但这确实会将一些私有 API 泄露给 public API.也许它对你有用and/or也许你并不关心。
;; 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 参数确实泄漏了一点私有 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)