使用 cons/car vs append 在 Racket 中创建列表

Question

我想制作一个方块列表。我可以使用以下代码来完成：

(define (makelistsq n)
  (define outlist '())
  (for ((i n))
    (set! outlist (append outlist (list (* i i))))
    )
  outlist
  )

(makelistsq 5)

输出：

'(0 1 4 9 16)

但是，我看到经常使用 cons 和 car 关键字来创建和添加到列表。这种方法比上面的附加方法有什么优势吗？那么，下面是更好还是与上面相同：

(define (makelistsq2 n)
  (define outlist '())
  (for ((i n))
    (set! outlist (cons (* i i) outlist))
    )
  (reverse outlist)
  )

感谢您的answers/comments。

编辑：在本页Cons element to list vs cons list to element in Scheme 中提到所有 append 的使用都是错误的：

For those rare occasions where you need to add one element at the end (and believe me, doing so generally means that you're thinking the algorithm wrong) you can use append

Answer 1

我不会重复我自己的回答 :P 。是的，使用 append 通常是构建输出列表的错误方法。但是你的实现似乎都不正确 - 大多数时候，你必须忘记 set! 和循环。

递归是可行的方法，在末尾使用 cons 和（如有必要）reverse 是构建列表的首选方法。其实题中的函数可以用内置程序表达得更简洁，写函数式代码时推荐这样写：

(define (makelistsq2 n)
  (map (lambda (x) (* x x))
       (range n)))

为了完整起见，让我们看看如何从头开始编写过程，使用 cons 构建输出 - 对于那些没有内置过程的罕见情况你需要。这会产生一个递归过程，注意这里我们从零到 n-1:

(define (makelistsq2 n)
  (define (helper i)
    (if (= i n)
        '()
        (cons (* i i)
              (helper (add1 i)))))
  (helper 0))

上述解决方案很好，非常适合小型列表。如果（且仅当）输出列表很大，您可能希望使用尾递归构建它；这是更有效的，因为它不需要额外的内存来进行迭代——我们将使用一个命名的 let，并注意这会生成一个迭代过程，从 n-1 到零：

(define (makelistsq2 n)
  (let loop ((i (sub1 n)) (acc '()))
    (if (negative? i)
        acc
        (loop (sub1 i) (cons (* i i) acc)))))

无论您选择哪种实现，现在的结果都符合预期：

(makelistsq2 5)
=> '(0 1 4 9 16)

Answer 2

cons 是一对的构造函数。列表只不过是 cons 链，以空列表 ().

结尾

append是在实现中使用了cons的函数。这是两个参数追加的实现：

(define (append lst1 lst2)
  (if (null? lst1)
      lst2
      (cons (car lst1) 
            (append (cdr lst1) lst2))))

用简单的英语来说，它为每对 lst1 生成一对新的，然后附加 lst2。它不是很有效，因此在您的第一个示例中，要生成该 5 元素列表，除了您为每个步骤明确制作的一个元素列表之外，它还必须制作一个 4、3 和 2 元素列表。

使用列表时，它会按从头到尾的顺序进行迭代，但列表的创建是从头到尾进行的。通常不可能反向做某事，因此最终需要反转结果，但在您的情况下，倒数而不是向上倒数很容易。

(define (make-square-list end)
  (let loop ((n (sub1 end)) (acc '()))
    (if (< n 0)
        acc
        (loop (sub1 n) 
              (cons (* n n) acc)))))

使用高阶函数，您可以消除样板文件，但 #!racket 有一个替代方案，可以生成更短的代码，称为 for/list。

(define (make-square-list end)
  (for/list ((n (range end)))
    (* n n)))

for/list 与 map 基本相同，但作为一种特殊形式。

Answer 3

我的版本：

#lang racket

(define (make-square-list n)
  (let loop ([count 1]
             [result_list '()])
    (if (<= count n)
        (loop (add1 count) (cons (* count count) result_list))
        (reverse result_list))))

(make-squqre-list 10)

(1 4 9 16 25 36 49 64 81 100)

使用 cons/car vs append 在 Racket 中创建列表

Using cons/car vs append to create lists in Racket

scheme

racket