functional-programming - letrec 有什么好处？

Question

在阅读“The Seasoned Schemer”时，我开始了解letrec。我了解它的作用(可以用 Y-Combinator 复制)，但本书使用它来代替对已经defined 函数的重复操作，该函数对保持静态的参数进行操作。

使用 defined 函数重复自身的旧函数示例(没什么特别的):

(define (substitute new old l)
  (cond
    ((null? l) '())
    ((eq? (car l) old)
      (cons new (substitute new old (cdr l))))
    (else
      (cons (car l) (substitute new old (cdr l))))))

现在举一个使用 letrec 的相同函数的例子:

(define (substitute new old l)
  (letrec
    ((replace
      (lambda (l)
        (cond
          ((null? l) '())
          ((eq? (car l) old)
           (cons new (replace (cdr l))))
          (else
           (cons (car l) (replace (cdr l))))))))
(replace lat)))

除了稍微长一点和更难读之外，我不知道他们为什么要重写书中的函数以使用 letrec。以这种方式重复静态变量时是否会提高速度，因为您不会一直传递它？？

这种标准做法是否适用于参数保持静态但有一个参数减少的函数(例如在列表的元素中重复出现)？

更有经验的 Schemers/LISPers 的一些意见会有所帮助!

Answer 1

因此，您有一些涵盖可读性问题的答案，应该没问题。但一个不清楚的问题是是否存在任何性能问题。粗略地看，letrec 版本，如命名-let 版本(实际上是相同的)似乎应该更快，因为要传递的参数更少在循环。然而，在实践中，编译器可以在你背后进行各种优化，比如弄清楚普通版本中的循环不改变地传递前两个参数，然后将它变成一个带有第一个参数的单参数循环。这里没有显示特定系统上的数字，而是一个 PLT 模块，您可以运行它来计时四个不同的版本，并且您可以轻松添加更多版本以尝试其他变体。简短的总结是，在我的机器上，named-let 版本稍快一些，使其成为尾递归具有更大的整体优势。

#lang scheme

;; original version
(define (substitute1 new old l)
  (cond [(null? l) '()]
        [(eq? (car l) old) (cons new (substitute1 new old (cdr l)))]
        [else (cons (car l) (substitute1 new old (cdr l)))]))

;; letrec version (implicitly through a named-let)
(define (substitute2 new old l)
  (let loop ([l l])
    (cond [(null? l) '()]
          [(eq? (car l) old) (cons new (loop (cdr l)))]
          [else (cons (car l) (loop (cdr l)))])))

;; making the code a little more compact
(define (substitute3 new old l)
  (let loop ([l l])
    (if (null? l)
      '()
      (cons (let ([fst (car l)]) (if (eq? fst old) new fst))
            (loop (cdr l))))))

;; a tail recursive version
(define (substitute4 new old l)
  (let loop ([l l] [r '()])
    (if (null? l)
      (reverse r)
      (loop (cdr l)
            (cons (let ([fst (car l)]) (if (eq? fst old) new fst)) r)))))

;; tests and timings

(define (rand-list n)
  (if (zero? n) '() (cons (random 10) (rand-list (sub1 n)))))

(for ([i (in-range 5)])
  (define l   (rand-list 10000000))
  (define new (random 10))
  (define old (random 10))
  (define-syntax-rule (run fun)
    (begin (printf "~a: " 'fun)
           (collect-garbage)
           (time (fun new old l))))
  ;; don't time the first one, since it allocates a new list to use later
  (define new-list (substitute1 new old l))
  (unless (and (equal? (run substitute1) new-list)
               (equal? (run substitute2) new-list)
               (equal? (run substitute3) new-list)
               (equal? (run substitute4) new-list))
    (error "poof"))
  (newline))