构建内置过程“build-list”在球拍 [英] Building the built-in procedure "build-list" in Racket

问题描述

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

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?

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

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

推荐答案

好的，所以你正在寻找一个不使用状态变量和尾调用的答案。您想要一个递归的过程，它也会产生一个递归的过程。不确定为什么你想要这个，而不仅仅是看看定义会有什么不同。您还应该阅读尾部递归模数缺点（此处，以及维基百科） - 与此问题相关。

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)

注意 aux 调用不再处于尾部位置 - 即 cons 在评估 aux 之前无法完成评估打电话给他们的论点。这个过程看起来像这样，在堆栈上演变：

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)

你会看到 cons 的电话在之前一直悬空。 。已填写。最后 ... 未填写清空直到 m 等于 n 。

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.

如果你不喜欢内部的 aux 程序，你可以使用默认参数，但这确实泄漏了一些私有API到公共API。也许它对你有用和/或你可能并不在乎。

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)

---

堆栈安全实施

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

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.

第一个是非常简单但使用 acc 参数泄漏了一点私有API。您可以使用 aux 轻松修复此问题像我们在第一个解决方案中所做的那样。

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)

查看演变过程

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

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.

最后，这是另一个演化线性迭代过程的递归过程。它使用了一个名为let和continuation的传递方式。循环有助于防止API泄漏。

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)

如果您使用<$ c $，它会清理一下c>撰写和咖喱：

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

从这个过程演变而来的过程略有不同，但你'请注意，它也不会增加堆栈，而是在堆上创建一系列嵌套的lambdas。所以这对于 n 的足够大的值就足够了：

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)

这篇关于构建内置过程“build-list”在球拍的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！