目录

• Translate to Scheme
• Review of Iteration via Tail Recursion
• Tail-Recursive Version of count
• Another Higher-Order Function Example: Map
• Reverse
• Tail-Recursive Reverse
• Trees Recursions

Translate to Scheme

将python program转换成Scheme version。

# python版本
def count(predicate, L):
    if L is Link.empty:
        return 0
    elif predicate(L.first):
        return 1 + count(predicate, L.rest)
    else:
        return count(predicate, L.rest)

# scheme版本
(define (count predicate L)
    (cond ((null? L) 0)
            ; ; (null? L) same as (eqv? L '()) or (eq? L '())
          ((predicate (car L))
           (+ 1 (count predicate (cdr L)))) ; Not a tail call
          (else (count predicate (cdr L)))) ; in cond, else == #t
)
(count odd? '(1 12 13 19 4 6 9))
(count odd? '())

Review of Iteration via Tail Recursion

Tail-Recursive Version of count

# python
def count(predicate, L):
    def count1(L, s):
        if L is Link.empty:
            return s
        elif predicate(L.first):
            return count1(L.rest, s + 1)
        else:
            return count1(L.rest, s)
    return count1(L, 0)

# scheme
(define (count predicate L)
    (define (count1 L s)
        (cond ((null? L) s)
              ((predicate (car L)) (count1 (cdr L) (+ s 1)))
              (#t (count1 (cdr L) s))))
         (count1 L 0)
)

Another Higher-Order Function Example: Map

# python
def map(fn, L):
    if L is Link.empty:
        return Link.empty
    else:
        return Link(fn(L.first), map(fn, L.rest))

# scheme
(define (map fn L)
    (if (null? L) '()
        (cons (fn (car L)) (map fn (cdr L))))
)

Reverse

Tail-Recursive Reverse

Trees Recursions