跳到主要内容

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

标签：

Author​

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

Description​

OCaml または Scheme で次を定義せよ。前の小問で定義した関数を用いてよい。

(1) 整数リスト items1 が items2 の前半部分であるとき真、それ以外は偽を返す prefix。どちらの入力リストの要素も二回以上辿らないこと。

(2) 関数 f とリスト items から、各要素に f を適用したリストを返す map。組込み map を使わず、入力要素を二回以上辿らないこと。

(3) items のすべての前半部分を短い順に並べる prefixes。入力要素を二回以上辿らないこと。例：prefixes [3;1;4] = [[];[3];[3;1];[3;1;4]]。

题目描述​

用 OCaml 或 Scheme 实现：(1) 判定一个整数列表是否为另一个列表的前缀。(2) 不用内置 map 实现映射函数。(3) 返回输入列表的全部前缀，按长度递增且包含空列表。每问都不得重复遍历输入列表的元素，可以调用前问函数。

Kai​

(1)​

let rec prefix items1 items2 =
  match items1, items2 with
  | [], _ -> true
  | _, [] -> false
  | x :: xs, y :: ys -> x = y && prefix xs ys

(2)​

let rec map f items =
  match items with
  | [] -> []
  | x :: xs ->
      let y = f x in
      y :: map f xs

(3)​

let rec prefixes items =
  match items with
  | [] -> [[]]
  | x :: xs ->
      [] :: map (fun ys -> x :: ys) (prefixes xs)

空リストの前半部分は空リストだけである。x :: xs の非空の前半部分は、xs の各前半部分に x を付けたものなので、帰納的に正しい順序で全前半部分を得る。元の入力リストは各再帰呼出しで頭と尾を一度だけ調べる。map が辿るのは生成された前半部分のリストである。

本页目录