• 検索結果がありません。

第 1 1 章 リ ス ト 1 . リ ス ト と は

N/A
N/A
Protected

Academic year: 2021

シェア "第 1 1 章 リ ス ト 1 . リ ス ト と は"

Copied!
5
0
0

読み込み中.... (全文を見る)

全文

(1)

第 1 1 章     リ ス ト

1 .   リ ス ト と は

  リ ス トと は 対 象 が 順 に 並 ん だ も の で あ る 。 最 も 単 純 な 形 の リ ス ト は 、 定 数 、 変 数 、 ま た は こ の 両 方 を 半 角 の 空 白 で 区 切 っ て 並 べ 、 全 体 を 丸 括 弧 で 囲 ん だ も の で あ る 。 リ ス ト の 中 に 含 ま れ る 対 象 を 、 リ ス ト の要 素と い う 。 そ の 要 素 の 数 を リ ス ト の長 さと い う 。 要 素 が 全 て 数 で あ る リ ス ト を数 リ ス トと い う 。

( 1 2 3 4 5 6)   (a b c d e f)   (*A *B *C *D *E *F)   (1 *X 3 4 *Y *Z)   

ま た 、 リ ス ト 自 体 も リ ス ト の 要 素 に な る こ と が で き る 。 こ れ を 「 リ ス ト の リ ス ト 」 と 呼 ん で い る 。 こ れ を 使 え ば 、 行 列 な ど を リ ス ト で 表 現 す る こ と も 可 能 で あ る 。 す な わ ち 行 列 の 1 行 を 数 リ ス ト で 表 し 、そ れ ら を 並 べ た リ ス ト を 作 れ ば 、「 リ ス ト の リ ス ト 」と し て 行 列 が 表 現 さ れ る 。

1 2 3 ((1 2 3) 4 5 6   →      (4 5 6) 7 8 9 (7 8 9))

  そ し て 、 要 素 が 全 く 含 ま れ て い な い も の も リ ス ト で あ り 、 そ れ を空 リ ス トと 呼 ぶ 。ET プ ロ グ ラ ミ ン グ で は 、 空 リ ス ト を ( ) と 書 き 、 リ ス ト の 長 さ は 0 で あ る 。

2 .   頭 部 と 尾 部

リ ス ト の頭 部と は 、 リ ス ト の 先 頭 の 要 素 で あ る 。 リ ス ト の尾 部は リ ス ト の 2 番 目 以 降 の 要 素 か ら な る リ ス ト で あ る 。 例 え ば 、(1 2 3 4 5 6) と い う リ ス ト の 頭 部 は 1 で あ り 、 尾 部 は リ ス ト (2 3 4 5 6) で あ る 。 逆 に 、 頭 部 が 1 、 尾 部 が (2 3 4 5 6) の リ ス ト は (1 2 3 4 5 6) で あ る 。 一 般 に 、 頭 部 と 尾 部 か ら 作 ら れ る 対 象 は 、( 頭 部 | 尾 部 ) の 形 に 書 か れ る 。 し た が っ て 、 頭 部 が 1 、 尾 部 が (2 3 4 5 6) の 場 合 に は 、 そ れ ら か ら 作 ら れ る 対 象 は 、(1|(2 3 4 5 6)) と な る 。 実 際 は (1 2 3 4 5 6) は (1|(2 3 4 5 6)) の 略 記 で あ り 、 両 者 は 全 く 同 じ リ ス ト を 表 し て い る 。そ の た め 、頭 部 が 1 、尾 部 が (2 3 4 5 6) の リ ス ト は (1 2 3 4 5 6) で あ る と い え る 。 以 下 の 式 を ETI に 入 力 し 、 直 接 実 行 し て 結 果 を 確 認 し な さ い 。

①   (= *X (1|(2 3 4 5 6)))

②   (= *X (1 2|(3 4 5 6)))

③   (= *X (1 |(2|(3 4 5 6))))

全 て(= *X (1 2 3 4 5 6)) に な る

(2)

こ れ ら の リ ス ト は 内 部 的 に は 全 く 同 一 の デ ー タ で あ る 。ETIは 、 そ の 最 も 簡 単 な 表 示 方 法 で あ る (1 2 3 4 5 6) を 用 い て 答 を 返 す 。

  リ ス ト は 縦 棒 を 用 い て (*A|*X) と 表 現 す る と 、頭 部 と 尾 部 は そ れ ぞ れ*A と*X に な る 。 尾 部 は リ ス ト で あ る の で 、(*X) と 表 現 し が ち で あ る が 、こ れ は 長 さ が 1 の リ ス ト を 意 味 す る の で 誤 り で あ る 。 仮 に (*A|*X) を (1|(2 3)) と し て 、 尾 部 を(*X)と 指 定 し て 取 り 出 す と ((2 3)) と な る 。こ れ は 、(2 3) を 要 素 と し た 長 さ 1 の リ ス ト( リ ス ト の リ ス ト )で あ る こ と を 意 味 し て い る 。

3 .   単 一 化 に よ る リ ス ト の 操 作

単 一 化 ( = ) と は 、 対 象 と な る 第 1 引 数 、 第 2 引 数 の 両 方 に 代 入 を 施 し 、 一 致 さ せ る 組 み 込 み 述 語 で あ る 。 単 一 化 は 両 方 の 引 数 に 代 入 を 施 す こ と が で き 、(= *A *B)と  (= *B *A) の よ う に 引 数 同 士 を 入 れ 替 え て も 結 果 は 変 わ ら な い 。 単 一 化 に よ っ て 、 対 象 が あ る 形 に な っ て い る か を 判 定 し た り 、 対 象 を 作 り 出 し た り す る こ と が で き る 。 例 え ば 、 リ ス ト の 頭 部 と 尾 部 を 求 め る た め に 、 単 一 化 を 使 う こ と が で き る 。 以 下 に 示 す ル ー ル を 記 述 し 、 質 問 を 与 え て 計 算 を 実 行 し な さ い 。

(ulA  *Y)  ‑‑>  (format  "(*A│*X)  と   /a  を 単 一 化 す る と 、 "  (*Y)),(ulA2  *Y). 

(ulA2 *Y),{(= (*A│*X) *Y)} ‑‑> (format "*A は  /a 、 *X は  /a に な る 。 /n" (*A *X)). 

(ulA2  *Y)  ‑‑>  (format  "失 敗 す る 。 /n"  (  )).

こ こ で 、format は ETI の 組 み 込 み 述 語 で あ り 、 (format  < 出 力 フ ォ ー ム >   < 対 象 リ ス ト > ) 

の シ ン タ ッ ク ス で 記 述 す る 。 例 え ば 「A は ×× 、B は ○ ○ に な る 」 と い う 文 を 表 示 さ せ た い と き 、format を 用 い て 以 下 の よ う に 記 述 す れ ば よ い 。

(format "A は  /a 、 B は  /a に な る 。 /n" (*A *B)) 

一 般 に format は 、 で 囲 ま れ た 文 字 列 を 出 力 す る 。 文 字 列 中 の /a や /n な ど は 制 御 記 号 で あ り 、/n は 改 行 を 表 し 、/a は 対 応 す る 対 象 に 置 き 換 え る こ と を 意 味 す る 。 対 応 す る 対 象 は format の 末 尾 に 書 か れ た 対 象 リ ス ト 内 に あ り 、 出 力 フ ォ ー ム の 左 か ら i 番 目 の /a が 、 対 象 リ ス ト 中 に あ る 第 i 番 目 の 要 素 の format 実 行 時 の 値 に 置 き 換 え ら れ る 。 し た が っ て 上 の 例 で は 、 ××と ○ ○ の 部 分 に は 、format 実 行 時 の*A、*B の 値 が 入 る 。  (ulA (1 2 3 4 5 6))と い う 質 問 を 入 れ る と 、 以 下 の よ う に 表 示 さ れ る 。

(3)

[D]> (ulA (1 2 3 4 5 6))

---D execution ---

(*A|*X) (1 2 3 4 5 6) を 単 一 化 す る と 、 * A は 1 、 *X は ( 2   3   4   5   6 )  に な る ---

succeeded.

(ulA (1 2 3 4 5 6))

execution time: 0 [msec]

同 様 に 、( ) 、(1)、 (1 2)、 (1 2 3)や 定 数 1、abc、 リ ス ト の リ ス ト ((1 2 3)(4 5 6)) の 場 合 も 実 行 し て み る と 、 そ れ ぞ れ の 質 問 に 対 し て 、 次 の よ う に 出 力 さ れ る 。

  (*A│*X) と ( ) を 単 一 化 す る と 、 失 敗 す る 。

  (*A│*X) と (1) を 単 一 化 す る と 、*A は 1、*X は ( ) に な る 。   (*A│*X) と (1 2) を 単 一 化 す る と 、*A は 1、*X は (2) に な る 。   (*A│*X) と (1 2 3) を 単 一 化 す る と 、*A は 1、*X は (2 3) に な る 。   (*A│*X) と 1 を 単 一 化 す る と 、 失 敗 す る 。

  (*A│*X) と abc を 単 一 化 す る と 、 失 敗 す る 。

  (*A│*X) と ((1 2 3)(4 5 6)) を 単 一 化 す る と 、*A は(1 2 3)、*X は ((4 5 6)) に な る 。

  さ ら に 、(= (*A│*X) *Y)の 引 数 同 士 を 入 れ 替 え て 、(= *Y (*A│*X))と し た 場 合 を 調 べ る 。 以 下 に 示 す ル ー ル を 記 述 し 、 質 問 を 与 え て 計 算 を 実 行 し な さ い 。

(ulB  *Y)  ‑‑>  (format  "(*A│*X)  と   /a  を 単 一 化 す る と 、 "  (*Y)),(ulB2  *Y). 

(ulB2 *Y),{(= *Y (*A│*X))} ‑‑> (format "*A は  /a 、 *X は  /a に な る 。 /n" (*A *X)). 

(ulB2  *Y)  ‑‑>  (format  "失 敗 す る 。 /n"  (  )). 

例 え ば 、 質 問 (ulB (1 2 3 4 5 6)) を 入 れ て 実 行 す る と 、 以 下 の よ う に 表 示 さ れ る 。

[D]> (ulB (1 2 3 4 5 6))

---D execution ---

(1   2   3   4   5  6 )  と ( * A│ * X) を 単 一 化 す る と 、 * A は 1 、 *X は ( 2   3   4   5   6 )  に な る

--- succeeded.

(ulB (1 2 3 4 5 6))

execution time: 0 [msec]

単 一 化 の 引 数 は 対 称 な の で 、ulB は ulA と 同 じ 結 果 を 与 え る 。

(4)

4 .   頭 部 の 要 素 を 2 つ に し た 場 合 の リ ス ト の 単 一 化

  (*A *B│*X) の パ タ ー ン と リ ス ト な ど を 単 一 化 さ せ た ら ど う な る か 。以 下 に 示 す プ ロ グ ラ ム を 記 述 し て 、 質 問(ulC (1 2 3 4 5 6))を 入 れ て 実 行 し な さ い 。

(ulC  *Y)  ‑‑>  (format  "(*A  *B│*X)  と   /a  を 単 一 化 す る と 、 "  (*Y)),(ulC2  *Y). 

(ulC2 *Y),{(= *Y (*A *B│*X))} 

  ‑‑>  (format  "*A  は   /a  、 *B  は   /a  、 *X  は   /a  に な る 。 /n"  (*A  *B  *X)). 

(ulC2  *Y)  ‑‑>  (format  失 敗 す る 。 /n   (  )). 

 

(ulC (1 2 3 4 5 6))を 与 え て 実 行 す る と 、 画 面 に は 以 下 の よ う に 表 示 さ れ る 。

[D]> (ulC (1 2 3 4 5 6))

---D execution ---

(* A  *B │* X )  と ( 1   2   3   4  5   6 )  を 単 一 化 す る と 、 * A =   1 、 * B=  2 、 * X =  (3  4  5   6)   に な る

--- succeeded.

(ulC (1 2 3 4 5 6))

execution time: 0 [msec]

同 様 に 、( ) 、(1)、 (1 2)、 (1 2 3)や 定 数 1、abc、 リ ス ト の リ ス ト ((1 2 3)(4 5 6)) の 場 合 も 実 行 し て み る と 、 そ れ ぞ れ の 質 問 に 対 し て 、 次 の よ う に 出 力 さ れ る 。

(*A *B│*X) と ( ) を 単 一 化 す る と 、 失 敗 す る 。 (*A *B│*X)と (1) を 単 一 化 す る と 、 失 敗 す る 。

(*A *B│*X)と (1 2) を 単 一 化 す る と 、*A は 1、*B は 2、*X は ( ) に な る 。 (*A *B│*X)と (1 2 3) を 単 一 化 す る と 、*A は 1、*B は 2、*X は (3) に な る 。 (*A *B│*X)と 1 を 単 一 化 す る と 、 失 敗 す る 。

(*A *B│*X)と abc を 単 一 化 す る と 、 失 敗 す る 。

(*A *B│*X) と ((1 2 3)(4 5 6)) を 単 一 化 す る と 、*A は(1 2 3)、*B は (4 5 6)、*Xは ( ) に な る 。

5 . リ ス ト の パ タ ー ン

  リ ス ト 処 理 で よ く 使 わ れ る パ タ ー ン を 列 挙 し て お こ う 。

( )     長 さ が 0 の リ ス ト

(5)

(*A *B)      長 さ が 2 の リ ス ト (*A *B│*X)    長 さ が 2 以 上 の リ ス ト

頭 部 をC A R(the Contents of the Address part of a Register の 略 語 、 カ ー と 言 う ) と 呼 び 、 尾 部 をC D R(the Contents of the Decrement part of a Registerの 略 語 、 ク ダ ー と 言 う )と 呼 ぶ こ と も あ る 。ま た 、C A R と C D R を 縦 棒 で 結 び つ け た 構 造 体 (CAR|CDR) の こ と を 、C O N S(コ ン ス と 言 う)と 呼 ぶ 。

6 .   簡 単 な リ ス ト 処 理

リ ス ト 処 理 を 行 う 上 で 、 先 頭 要 素 の 抽 出 、 先 頭 要 素 の 除 去 、 リ ス ト 合 成 は 基 本 的 な 操 作 で あ る 。 先 頭 要 素 の 抽 出 と は リ ス ト の 先 頭 の 要 素 を 求 め る こ と で あ る 。 先 頭 要 素 の 除 去 と は 、 リ ス ト の 先 頭 の 要 素 を 取 り 除 い た リ ス ト を 与 え る こ と で あ り 、 尾 部 だ け を 抽 出 す る 。 リ ス ト 合 成 は 対 象 と リ ス ト か ら 新 た な リ ス ト を 作 る 。 次 の 述 語 を 考 え る 。

(first *x *y) ・・・ *y は*xの 頭 部 で あ る 。 (rest *x *y) ・・・ *yは*xの 尾 部 で あ る 。

(cons *a *b  *y) ・・・ *y は*aを 頭 部 、*bを 尾 部 と す る 構 造 体 で あ る 。 こ れ ら の 述 語 を 処 理 す る た め に 、 次 の ル ー ル を 記 述 し な さ い 。

; 先 頭 要 素 の 抽 出 ( リ ス ト の 頭 部 を 求 め る ) (first (*A│*B) *Y) ‑‑> (= *Y *A). 

; 先 頭 要 素 の 除 去 ( リ ス ト の 尾 部 を 求 め る ) (rest (*A│*B) *Y) ‑‑> (= *Y *B). 

; リ ス ト 合 成 ( 対 象 と リ ス ト か ら 新 た な リ ス ト を 作 る ) (cons *A *X *Y) ‑‑> (= *Y (*A│*X)). 

  記 述 し 終 え た ら 、ETIを 起 動 し て 質 問 (first (1 2 3 4 5 6) *Y)、(rest (1 2 3 4 5 6) 

*Y)、(cons 0 (1 2 3 4 5 6) *Y) を 入 れ て 、 計 算 を 実 行 し な さ い 。

  こ の 結 果 、 先 頭 要 素 を 抽 出 す る と *Y は 1 と な り 、 先 頭 要 素 を 除 去 す る と (2 3 4 5 6)と な り 、 リ ス ト 合 成 を 行 う と (0 1 2 3 4 5 6) と そ れ ぞ れ 答 が 求 ま る 。

参照

関連したドキュメント

⑥ニューマチックケーソン 職種 設計計画 設計計算 設計図 数量計算 照査 報告書作成 合計.. 設計計画 設計計算 設計図 数量計算

・石川DMAT及び県内の医 療救護班の出動要請 ・国及び他の都道府県へのD MAT及び医療救護班の派 遣要請

平成25年3月1日 東京都北区長.. 第1章 第2章 第3 章 第4章 第5章 第6章 第7 章

掘取り 運搬 植穴床掘 植え付け 跡片付け.. 22

(1)東北地方太平洋沖地震発生直後の物揚場の状況 【撮影年月日(集約日):H23.3.11】 撮影者:当社社員 5/600枚.

第1章 防災体制の確立 第1節 防災体制

1000 ㎥/日以上の事業者 213.5 73.2 140.3 65.7 500 ㎥/日以上の事業者 39.3 18.6 20.8 52.9 200 ㎥/日以上の事業者 20.4 19.1 1.3 6.3. 計 273.3 110.9 162.4

[r]