1

我学习过编程语言课程，幻灯片中有这个 Scheme 代码的变体：

; (listof any) -> (listof any[no-cons])

(define (remove-pairs l)
  (cond
    [(empty? l) '()]
    [else
      (let ([ans
              (if (cons? (first l))
                  (begin (free! (first l))
                         (remove-pairs (rest l)))
                  (cons (first l)
                        (remove-pairs (rest l))))])
       (free! l) ; <- this will break our tail recursion.
       ans)]))

在代码中，(free! l)会破坏我们的尾递归。我不知道这个功能是做什么的，我无法理解。

4

1 回答 1

0

不看代码就不可能知道这个函数应该做什么free!。可以推断的是，该过程删除列表中不是cons单元格的每个元素，构建并返回一个新列表，其中仅包含cons从一开始就不是单元格的元素。

说函数是尾递归的是不正确的——它从来没有开始，无论做什么free!，递归调用都不在尾位置。

这是使用尾递归实现推断功能的正确方法，请注意问题中递归的结构方式是完全错误的，根本不是尾递归：

(define (remove-pairs l)
  (let loop ((lst (reverse l))
             (acc '()))
    (cond [(empty? lst)
           acc]
          [(cons? (first lst))
           (free! (first lst)) ; whatever that is
           (loop (rest lst) acc)]
          [else
           (loop (rest lst) (cons (first lst) acc))])))

从更实际的角度来看，您可以使用 获得相同的功能filter，尽管这不能保证是尾递归：

(define (remove-pairs l)
  (filter (lambda (x)
            (cond [(cons? x)
                   (free! x) ; whatever that is
                   #f]
                  [else #t]))
          l))

无论哪种方式，它都是这样工作的：

(remove-pairs '(1 (2 4) 3 5 (6 8) 7 (9 11)))
=> '(1 3 5 7)
于 2013-06-22T13:41:18.550 回答