千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2018年8月実施 専門 B12

标签：

• 高阶函数
• 闭包
• 递归

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

次の Scheme プログラムについて理由付きで答えよ。

(define (r x) (lambda (z) x))
(define (b g f) (lambda (z) ((f (g z)) z)))
(define t1 (b (lambda (z) (* 2 z)) r))
(define t2
  (b car (lambda (u) (b cadr (lambda (v) (r (+ u v)))))))
(define (tn f a)
  (if (null? f) (r a)
      (b (car f) (lambda (u) (tn (cdr f) (cons u a))))))

(1) (t1 2) の値を求めよ。(2) (t2 'ℓ) の値が $0$ となる式 $\ell$ を特徴付けよ。(3) $\ell$ をリストとしたとき ((tn (list cadr car caddr) '(0)) 'ℓ) の値を求めよ。

题目描述

阅读上述 Scheme 程序并说明理由。(1) 求 (t1 2)。(2) 描述使 (t2 'ℓ) 返回零的表达式 $\ell$。(3) 当 $\ell$ 为列表时，求指定 tn 调用的结果。

Kai

(1) 定義から $(b\ g\ f)(z)=f(g(z))(z)$ であり、$r(x)$ は定数関数である。従って t1 は $z\mapsto2z$ で、答えは 4。

(2) 定義を展開すると

(t2 l) = (+ (car l) (cadr l))

である。従って先頭2要素が数値で、その和が $0$ となる必要十分条件を満たせばよい。通常のリストなら (a (-a) ...) の形、すなわち第1要素が数 $a$、第2要素が数 $-a$ のリストである（(-a) は評価する式ではなく数値 $-a$ を意味する）。car と cadr が定義されれば、残りの末尾は任意でもよい。

(3) $\ell=(\ell_1\ \ell_2\ \ell_3\ \ldots)$ とする。tn は各関数を同じ引数 $\ell$ に適用し、その結果を順に累積リストの先頭へ追加する。従って

(0) -> (l2 0) -> (l1 l2 0) -> (l3 l1 l2 0)

となり、評価結果は (ℓ3 ℓ1 ℓ2 0)。要素が3個未満なら caddr を適用できず、通常はエラーとなる。