在阅读《老练的阴谋家》时,我开始了解letrec
。我理解它的作用(可以用 Y-Combinator 复制),但这本书正在使用它来代替已经重复出现的内容define
d 函数对保持静态的参数进行操作。
使用旧函数的示例define
d 函数本身重复出现(没什么特别的):
(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。当以这种方式重复静态变量时,速度是否会提高,因为您不继续传递它?
对于参数保持静态但一个参数减少的函数(例如重复出现列表的元素),这是标准做法吗?
来自更有经验的策划者/LISPers 的一些意见将会有所帮助!
所以你有一些涵盖可读性问题的答案,这应该没问题。但有一个问题尚不清楚,即是否存在性能问题。粗略地看,似乎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))
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)