跳到主要内容

千葉大学 理学研究科 基盤理学専攻 数学・情報数理学コース 2013年8月実施 専門 B11

标签：

Author​

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

Description​

次の Scheme プログラムを考える。

(define (fold-right f c s)
  (if (null? s) c
      (f (car s) (fold-right f c (cdr s)))))
(define (flatten ss) (fold-right append '() ss))
(define (map f s)
  (fold-right (lambda (x y) (cons (f x) y)) '() s))
(define (mmap f ss) (map (lambda (s) (map f s)) ss))
(define (flatten-mmap f ss) (flatten (mmap f ss)))

(1) リスト s,ts,t を連結し、cons の呼出回数が ss の長さになる append を、再帰を直接使わず fold-right により定義せよ。

(2) ss が長さ nn のリストを mm 個並べたリストであるとき、flatten と mmap の cons の総呼出回数を求めよ。

(3) flatten-mmap の引数と返り値の関係を説明せよ。

(4) 同じ返り値をもち、cons の総呼出回数が返り値の長さに等しい関数 fm を定義せよ。以上、引数 f 自身による cons は数えない。

题目描述​

考虑上述 Scheme 程序。(1) 用 fold-right、不直接递归定义连接两个列表的 append，要求 cons 次数等于首列表长度。(2) 若输入包含 mm 个长度为 nn 的列表，求 flatten、mmap 的 cons 次数。(3) 说明 flatten-mmap 的功能。(4) 定义等价的 fm，使 cons 次数恰等于输出列表长度。均不计函数参数 f 内部的 cons。

Kai​

(1)​

(define (append s t)
  (fold-right cons t s))

(2)​

flatten は各内側リストを一度ずつコピーするので mn\boxed{mn} 回。mmap は内側の各要素に mnmn 回、外側のリストを作るために mm 回使用するので mn+m\boxed{mn+m} 回。

(3)​

各内側リストの各要素に f を適用し、元の順序のまま一つのリストに連結する。例えば ss = ((a b) (c)) なら返り値は ((f a) (f b) (f c)) に対応する値のリストである。

(4)​

(define (fm f ss)
  (fold-right
    (lambda (s tail)
      (fold-right
        (lambda (x rest) (cons (f x) rest))
        tail s))
    '() ss))

内側の fold-right が各入力要素につきちょうど一度 cons を呼び、外側では呼ばない。したがって総呼出回数は返り値の長さに等しい。

本页目录