技巧向

2016-07-28
2分钟阅读时长
Scheme

不用letrec递归

由于 tail-calls 可以看做是一个简单的jumps

尾递归(tail recursion)会减少stack的使用

(letrec ([sum (lambda (ls)
                (if (null? ls)
                    0
                    (+ (car ls) (sum (cdr ls)))))])
  (sum '(1 2 3 4 5)))
(let ([sum (lambda (sum ls)
             (if (null? ls)
                 0
                 (+ (car ls) (sum sum (cdr ls)))))])
  (sum sum '(1 2 3 4 5)))

判断list是否有圈

Floyd判圈算法: 如果两个人同时出发，如果赛道有环，那么快的一方总能追上慢的一方

(define (list? x)
  (define (race h t)
    (if (pair? h)
        (let ([h-cdr (cdr h)])
          (if (pair? h-cdr)
              (and (not (eq? h-cdr t))
                   (race (cdr h-cdr) (cdr t))) ;; h 每次两步, t 每次一步
              (null? h-cdr)))
        (null? h)))
  (race x x))

let的正确调用方式

(named let)

(let name ((var expr) ...)
  body1 body2 ...)
;; 等价于
((letrec ((name (lambda (var ...) body1 body2 ...)))
   name)
 expr ...)
;; 等价于
(letrec ((name (lambda (var ...) body1 body2 ...)))
  (name expr ...))

举个栗子

(define (factorial n)
  (let fact ([i n])
    (if (= i 0)
        1
        (* i (fact (- i 1)))))) ;; 可递归

等价于

(define (factorial n)
  ((letrec ((fact (lambda [i]
                    (if (= i 0)
                        1
                        (* i (fact (- i 1))))
                    )))
     fact) n))

等价于

(define (factorial n)
  (letrec ((fact (lambda [i]
                   (if (= i 0)
                       1
                       (* i (fact (- i 1))))
                   )))
    (fact n)))

简而言之

(let f ([m 3] [n 2]) (+ m n))
;; 等价于
((letrec ([f (lambda (m n) (+ m n))]) f) ;; 定义f并返回
    2 3)
(letrec ([f (lambda (m n) (+ m n))]) (f 2 3))

关于named let的正确使用方式

;; 斐波那契数列(此链接其实并无luan用) 的简易实用定义
(define fibonacci
  (lambda (n)
    (if (= n 0)
        0
        (let fib ([i n] [a1 1] [a2 0])
          (if (= i 1)
              a1
              (fib (- i 1) (+ a1 a2) a1))))))

机智的尾递归

看代码

(define-syntax or
  (syntax-rules ()
    [(_) #f]
    [(_ e) e] ;; it can tail recursive
    [(_ t e1 e2 ...) (if t t (or e1 e2 ...))]))

没有什么问题, 而对于

(define-syntax kor
  (syntax-rules ()
    [(_) #f]
    [(_ t e1 ...) (if t t (kor e1 ...))]))

看起来精简一点, 但是存在一个微妙的bug

尝试运行

(letrec ([even?
          (lambda (x)
            (kor (= x 0)
                 (odd? (- x 1))))]
         [odd?
          (lambda (x)
            (and (not (= x 0))
                 (even? (- x 1))))])
  (even? 99999999))
(even? 99999999)
=> (if (= 99999999 0) (= 99999999 0) (kor (odd? 99999998)))
=> (if (= 99999999 0) (= 99999999 0) (if (odd? 99999998) *(odd? 99999998)* (kor)))
=> (if (= 99999999 0) (= 99999999 0) (if (odd? 99999998) *(odd? 99999998)* #f)))

这里 (odd? 99999998) 并不在函数末尾, 浪费了大量内存

而用or的过程

(even? 99999999)
=> (if (= 99999999 0) (= 99999999 0) (kor (odd? 99999998)))
=> (if (= 99999999 0) (= 99999999 0) (odd? 99999998))

则神奇的变成了尾递归

#Scheme
上一页 不动点组合子
下一页 Emacs手记

相关

CPS变换
Lambda表达式
Macro
不动点组合子