letrec有什么好处？

Question

在阅读"The Seasoned Schemer"时,我开始学习letrec.我理解它的作用(可以用Y-Combinator复制),但本书正在使用它来代替在已define保持静态参数的已经d函数上重复出现.

使用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模块,可以运行四个不同的版本,而不是向您显示特定系统上的数字,您可以轻松添加更多以尝试其他变体.简短的总结是在我的机器上,命名 - 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))