本文介绍了letrec有什么好处?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

阅读The Seasoned Schemer时,我已经开始了解 letrec 。我明白它的作用(可以用Y-Combinator复制),但是本书使用它来代替对 define d函数的循环操作,该函数对保持静态的参数进行操作。

一个使用 define d函数的旧函数自身重复使用的例子(没有特别的):

p>

 (define(replace new old l)
(cond
((null?l)'())
((eq?(car l)old)
(cons new(替代new old(cdr l))))
(else
(cons(car l)新旧(cdr l))))))

现在, letrec

 (define(替换new old l)$ b $ (b)(b)(b)(b)(b)(b)(b)(b) )old 
(cons new(replace(cdr l))))
(else
(cons(car l)(replace(cdr l))) )))))
(取代拉特)))

更难阅读我不知道他们为什么要重写本书中的函数来使用letrec。是否有一个速度增强,当这种方式通过静态变量重复发生时,因为您不会继续传递它?



对于参数保持静态的函数,这是标准做法吗?减少一个参数(例如重复列表中的元素)?

来自更有经验的Schemers / LISPers的一些输入将会有所帮助!

$ b $所以你有几个覆盖可读性问题的答案,这应该没问题。但一个不清楚的问题是是否有任何性能问题。从表面上看,似乎 letrec 版本,就像命名 - let 一样(这真的是一样的)应该更快,因为循环中传递的参数较少。但是,在实践中,编译器可以在背后进行各种优化,例如找出普通版本中的循环将前两个参数保持不变,然后将其转换为第一个参数的单参数循环。 PLT模块不是向您显示特定系统上的数字,而是您可以运行四个不同版本的PLT模块,并且您可以轻松添加更多以尝试其他变体。简短的总结是,在我的机器上,名为 - let 版本稍微快一些,并且使其尾部递归具有更大的总体收益。

  #lang scheme 

;;原始版本
(define(substitute1 new old l)
(cond [(null?l)'()]
[(eq?(car l)old)(cons new(substitute1 new旧的(cdr l)))]
[else(cons(car l)(substitute1 new old(cdr l)))]))

;; letrec版本(隐式地通过named-let)
(define(substitute2 new old l)
(let loop([ll])
(cond [(null?l)'()]
[(eq?(car l)old)(cons new(loop(cdr l)))]
[else(cons(car l)(loop(cdr l)))])))

;;使得代码更加紧凑
(define(substitute3 new old l)
(let loop([ll])
(if(null?l)
'()
(cons(let([fst(car l)])(if(eq?fst old)new fst))
(loop(cdr l))))))

;;一个尾递归版本
(define(substitute4 new old l)
(let loop([ll] [r'()])
(if(null?l)
反向r)
(循环(cdr l)
(cons(let([fst(car l)])(if(eq?fst old)new fst))r))))

;;测试和计时
$ b $(define(rand-list n)
(if(zero?n)'()(cons(random 10)(rand-list(sub1 n))))) )
$ b $(定义新(随机10))$ b(for([i(in-range 5)])
(define l(rand-list 10000000))$ b $ $ b(define old(random 10))
(define-syntax-rule(run fun)
(begin(printf〜a:'fun)
(collect-garbage)
(time(fun new old l))))
;;不要计算第一个,因为它会分配一个新列表以便稍后使用
(define new-list(substitute1 new old l))
(除非(和(等于?(运行substitute1)新列表)
(等于?(运行substitute2)新列表)
(等于?(运行substitute3)new-列表)
(等于?(运行substitute4)new-list))
(errorpoof))
(newline))
pre>

While reading "The Seasoned Schemer" I've begun to learn about letrec. I understand what it does (can be duplicated with a Y-Combinator) but the book is using it in lieu of recurring on the already defined function operating on arguments that remain static.

An example of an old function using the defined function recurring on itself (nothing special):

(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))))))

Now for an example of that same function but using 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)))

Aside from being slightly longer and more difficult to read I don't know why they are rewriting functions in the book to use letrec. Is there a speed enhancement when recurring over a static variable this way because you don't keep passing it??

Is this standard practice for functions with arguments that remain static but one argument that is reduced (such as recurring down the elements of a list)?

Some input from more experienced Schemers/LISPers would help!

解决方案

So you have a few answers that cover the readability issue, which should be fine. But one question that is unclear is whether there are any performance issues. On a shallow look, it seems that the letrec version, like the named-let one (which is really the same) should be faster since there are less arguments to pass around in the loop. However, in practice compilers can do all kinds of optimizations behind your back, like figure out that the loop in the plain version passes the first two arguments unchanged, and turn it into a single-argument loop with the first one. Instead of showing you the numbers on a particular system, here is a PLT module that you can run to time four different versions, and you can easily add more to try out other variations. The short summary is that on my machine, the named-let version is slightly faster, and making it tail-recursive has a larger overall benefit.

#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))

这篇关于letrec有什么好处?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

07-23 07:00
查看更多