sp-7. リストの生成

sp-7. リストの生成 （Scheme プログラミング） URL: https://www.kkaneko.jp/pro/scheme/index.html 金子邦彦 1

• https://www.kkaneko.jp/pro/scheme/index.html

アウトライン 7-1 リストの生成 リストを「出力」とするような関数 cons を使用 リストのリスト(リストの入れ子）の生成 7-2 パソコン演習 7-3 課題 2

7-1 リストの生成 3

リストの表記 • cons による表記 例） (cons 'x (cons 'y (cons 'z empty))) • list による表記 「empty」は空リストの意味 であったが，ここでは，末尾 の意味になる 例） (list 'x 'y 'y) ２種類の表記がある 4

実行結果の例 5

コンピュータが行っていること Scheme の式 例えば： (cons 'x (cons 'y empty)) を入力すると・・・ コンピュータ (Scheme 搭載) 式の実行結果 (list 'x 'y) が表示される 6

cons の実行例 (cons 'x empty) → (list 'x) (cons 'x (cons 'y empty)) → (list 'x 'y) (cons 'x (cons 'y (cons 'z empty))) → (list 'x 'y 'z) 7

cons の意味 (cons 'x (cons 'y (cons 'z empty))) x y z x, y, z のリスト 8

cons の意味 cons は，リストの first と rest をつなげて，リストを作る 'x 'x 'y 'y 'z empty 'z first リスト empty リスト empty リスト rest 'y 'z rest first 'z first empty rest リスト 9

リストと cons の関係 1. 空リスト • empty 2. 長さ１以上のリスト • • list 形式: 例 (list 12 24 26) cons 形式： 例 (cons 12 (cons 24 (cons 36 empty))) この２つは同じ意味 10

Scheme の式の構成物 • 数値： 5, -5, 0.5 など • true, false 値 true, false • シンボル，文字列 • 変数名 • empty • 四則演算子： +, -, *, / • 比較演算子 <, <=, >, >=, = • 奇数か偶数かの判定 odd?, even? • 論理演算子 and, or, not • リストに関する演算子 first, rest, empty?, length, list-ref, append, cons • その他の演算子： remainder, quotient, max, min, abs, sqrt, expt, log, sin, cos, tan asin, acos, atan など • 括弧 • • • • (, ), [, ] 関数名 define cond list 11

7-2 パソコン演習 12

パソコン演習の進め方 • 資料を見ながら，「例題」を行ってみる • 各自，「課題」に挑戦する • 各自で自習 ＋ 巡回指導 • 自分のペースで先に進んで構いません 13

DrScheme の使用 • DrScheme の起動 プログラム • → PLT Scheme → DrScheme 今日の演習では「Intermediate Student」 に設定 Language → Choose Language → Intermediate Student → Execute ボタン 14

例題１．２次方程式 ２次方程式 ax2 + bx + c = 0 の解を求める関数 quadratic-roots を作り，実行する • • 解を「リスト」として出力する • 重解を求める • 但し，虚数解は考えない • a=0 の場合も考えない 参考 Webページ： http://www.htdp.org/2001-11-21/Book/node57.htm: Exercise 10.1.8 15

• http://www.htdp.org/2001-11-21/Book/node57.htm

• 一変数 x の二次方程式の一般形: • ax2 + bx + c = 0 二次方程式の解の数: a, b, cの値に依存 (1) a = 0 ⇒ 方程式は degenerate (2) a ≠ 0 ⇒ proper な二次方程式 1. もし b2 > 4ac なら 二つの解 2. もし b2 = 4ac なら 一つの解 3. もし b2 < 4ac なら 解無し 16

判別式 D = b2 - 4ac とする 1) D > 0 のとき −b+ D −b− D 異なる２実数解 x= , 2a 2a 2) D = 0 のとき b x = − , 重解（解の個数は１） 2a 3) D < 0 のとき 解なし 17

「例題１．２次方程式」の手順 1. 次を「定義用ウインドウ」で，実行しなさい • 入力した後に，Execute ボタンを押す (define (D a b c) (- (* b b) (* 4 a c))) (define (quadratic-roots a b c) (cond [(< (D a b c) 0) 'None] [(= (D a b c) 0) (- (/ b (* 2 a)))] [else (list (/ (+ (- b) (sqrt (D a b c))) (* 2 a)) (/ (+ (- b) (- (sqrt (D a b c)))) (* 2 a)))]) 2. その後，次を「実行用ウインドウ」で実行しなさい (quadratic-roots 1 -5 6) (quadratic-roots 2 0 -1) (quadratic-roots 1 2 1) (quadratic-roots 1 0 1) ☆ 次は，例題２に進んでください 18

まず，Scheme のプログラムを コンピュータに読み込ませている 19

実行結果が，リスト，数値，シンボル で得られている 20

入力と出力 quadratic-roots 入力 入力は ３つの数値 出力 出力は ・１つのリスト ・１つの数値 ・シンボル 'None のどれか 21

quadraric-roots 関数 (define (D a b c) (- (* b b) (* 4 a c))) (define (quadratic-roots a b c) (cond [(< (D a b c) 0) 'None] [(= (D a b c) 0) (- (/ b (* 2 a)))] [else (list (/ (+ (- b) (sqrt (D a b c))) (* 2 a)) (/ (+ (- b) (- (sqrt (D a b c)))) (* 2 a)))]) 22

例題２．リストの生成 • n 個の数字 「1」 を要素とするリス トを生成する関数 1list を作り，実 行する • cons を使用する 23

「例題２．リストの生成」の手順 1. 次を「定義用ウインドウ」で，実行しなさい • 入力した後に，Execute ボタンを押す (define (1list n) (cond [(= n 0) empty] [else (cons 1 (1list (- n 1)))])) 2. その後，次を「実行用ウインドウ」で実行しなさい (1list 0) (1list 3) ☆ 次は，例題３に進んでください 24

まず，Scheme のプログラムを コンピュータに読み込ませている 25

これは， (1list 3) と書いて，n の値を 3 に設定しての実行 実行結果である「(list 1 1 1)」が 表示される 26

入力と出力 3 (list 1 1 1) 1list 入力 入力は １つの数値 出力 出力は １つのリスト 27

1list 関数 ;;1list: number -> list-of-numbers ;; to create a list of n copies of 1 ;; (1list 0) = empty ;; (1list 3) = (list 1 1 1) (define (1list n) (cond [(= n 0) empty] [else (cons 1 (1list (- n 1)))])) 28

リストの生成 1. n = 0 ならば： empty → 終了条件 → 自明な解 2. そうで無ければ： – 長さ n-1 のリストを作り，その先頭に 「１」をつなげる – リストの先頭に「１」をつなげるため に，cons を使う 29

リストの生成 1list • 1list の内部に 1list が登場 (define (1list n) (cond [(= n 0) empty] [else (cons 1 (1list (- n 1)))])) • 1list の実行が繰り返される 例：(1list 3) = (cons 1 (1list 2)) 30

例題３．ステップ実行 • 関数 1list （例題２）について，実行結果に至る過 程を見る • (1list 3) から (list 1 1 1) に至る過程を見る • DrScheme の stepper を使用する (define (1list n) (1list 3) (cond =… [(= n 0) empty] = (cons 1 (1list 2)) [else (cons 1 (1list (- n 1)))])) =… (1list 3) = (cons 1 (cons 1 (1list 1))) =… = (cons 1 (cons 1 (cons 1 (1list 0)))) =… = (cons 1 (cons 1 (cons 1 empty))) = (list 1 1 1) 31

「例題３．ステップ実行」の手順 1. 次を「定義用ウインドウ」で，実行しなさい • Intermediate Student で実行すること • 入力した後に，Execute ボタンを押す (define (1list n) (cond [(= n 0) empty] [else (cons 1 (1list (- n 1)))])) (1list 3) 例題２と同じ 2. DrScheme を使って，ステップ実行の様子を 確認しなさい （Step ボタン，Next ボタンを使用） • 理解しながら進むこと ☆ 次は，例題４に進んでください 32

(1list 3) から (list 1 1 1) が得られる過程の概略 最初の式 (1list 3) =… = (cons 1 (1list 2)) =… = (cons 1 (cons 1 (1list 1))) =… = (cons 1 (cons 1 (cons 1 (1list 0)))) =… = (cons 1 (cons 1 (cons 1 empty))) コンピュータ内部での計算 = (list 1 1 1) 実行結果 33

(1list 3) から (cons 1 (1list 2)) が得られる過程 (1list 3) (1list 3) = (cond =… この [(= 3 0) empty] = (cons 1 (1list 2)) 部分は [else (cons 1 (1list (- 3 1)))]) =… = (cond = (cons 1 (cons 1 (1list 1))) [false empty] =… [else (cons 1 (1list (- 3 1)))]) = (cons 1 (cons 1 (cons 1 (1list = (cons 0))))1 (1list (- 3 1))) = (cons 1 (1list 2)) =… = (cons 1 (cons 1 (cons 1 empty))) = (list 1 1 1) 34

(1list 3) から (cons 1 (1list 2)) が得られる過程 (1list 3) (1list 3) = (cond =… この [(= 3 0) empty] = (cons 1 (1list 2)) 部分は [else (cons 1 (1list (- 3 1)))]) =… = (cond = (cons 1 (cons 1 (1list 1))) [false empty] これは， =… [else (cons 1 (1list (- 3 1)))]) (define (1list n) = (cons 1 (cons 1 (cons 1 (1list = (cons 0))))1 (1list (- 3 1))) (cond = (cons 1 (1list 2)) =… [(= n 0) empty] (cons 1 (1list (- n 1)))])) = (cons [else 1 (cons 1 (cons 1 empty))) を131)で置き換えたもの =の (listn 1 35

例題４．リストの生成 • n 個のシンボル 「'*」 を要素とする リストを生成する関数 astlist を作り， 実行する • cons を使用する 36

「例題４．リストの生成」の手順 1. 次を「定義用ウインドウ」で，実行しなさい • 入力した後に，Execute ボタンを押す (define (astlist n) (cond [(= n 0) empty] [else (cons '* (astlist (- n 1)))])) 2. その後，次を「実行用ウインドウ」で実行しなさい (astlist 0) (astlist 3) (astlist 10) ☆ 次は，例題５に進んでください 37

実行結果の例 38

入力と出力 3 (list '* '* '*) astlist 入力 入力は数値 出力 出力はリスト 39

リストの生成 1. n = 0 ならば： empty → 終了条件 → 自明な解 2. そうで無ければ： – 長さ n-1 のリストを作り，その先頭に 「'*」をつなげる – リストの先頭に「'*」をつなげるために， cons を使う 40

astlist 関数 ;; astlist: number -> list of symbols ;; to create a list of n copies of '* ;; (astlist 0) = empty ;; (astlist 3) = (list '* '* '*) (define (astlist n) (cond [(= n 0) empty] [else (cons '* (astlist (- n 1)))])) 41

(astlist 3) から (list '* '* '*) が得られる過程の概略 = (astlist 3) =… = (cons '* (astlist 2)) =… = (cons '* (cons '* (astlist 1))) =… = (cons '* (cons '* (cons '* (astlist 0)))) =… = (cons '* (cons '* (cons '* empty))) = (list '* '* '*) 42

例題５．賃金リストの生成 • 賃金を求める関数 wage を作り実行する • 従業員について 賃金 ＝ １２×勤務時間 • 全従業員の勤務時間のリスト alon から，賃金 のリストを生成する関数 hours->wages を作 り，実行する • 関数 wage を使う 43

「例題５．賃金リストの生成」の手順 1. 次を「定義用ウインドウ」で，実行しなさい • 入力した後に，Execute ボタンを押す (define (hours->wages alon) (cond [(empty? alon) empty] [else (cons (wage (first alon)) (hours->wages (rest alon)))])) (define (wage h) (* 12 h)) 2. その後，次を「実行用ウインドウ」で実行しなさい (hours->wages (list 5 3 6)) (hours->wages (list 100 200 300 400)) (hours->wages empty) ☆ 次は，例題６に進んでください 44

まず，Scheme のプログラムを コンピュータに読み込ませている 45

これは， (hours->wages (list 5 3 6)) と書いて，alon の値を (list 5 3 6) に設定しての実行 実行結果である「(list 60 36 72)」が 表示される 46

入力と出力 (list 60 36 72) (list 5 3 6) hours->wages 入力 入力は １つのリスト 出力 出力は １つのリスト 47

;; hours->wages: list-of-numbers -> list-of-numbers ;; to create a list of weekly wages from a list of ;; weekly hours(alon) ;; Example: (hours->wages (list 5 3 6)) = (list 60 36 72) (define (hours->wages alon) (cond [(empty? alon) empty] [else (cons (wage (first alon)) (hours->wages (rest alon)))])) ;;wage: number->number ;;to compute the total wages(at $12 per hour) ;;of someone who worked for h hours ;; Example: (wage 5) = 60 (define (wage h) (* 12 h)) 48

賃金リストの生成 1. リストが空ならば： empty → 終了条件 → 自明な解 2. そうで無ければ： – 「勤務時間のリストの rest に対する hours>wages の結果（リスト）の先頭に，勤務時間 の first に対する wage の結果（数値）をつなげ たもの」 が求める解 – リストの先頭に数値をつなげるために，cons を 使う 49

賃金リストの生成 • hours->wages の内部に hours->wages が登場 (define (hours->wages alon) (cond [(empty? alon) empty] [else (cons (wage (first alon)) (hours->wages (rest alon)))])) • hours->wages の実行が繰り返される 例： (cons (wage 1) (hours->wages (list 2 3))) 50

例題６．ステップ実行 • 関数 hours-wage （例題５）について，実行結果 に至る過程を見る • (hours->wage (list 1 2 3)) から (list 12 24 36) に至る過 程を見る • DrScheme の stepper を使用する (hours->wages (list 1 2 3)) =… = (cons (wage 1) (hours->wages (rest (list 1 2 3)))) =… = (cons 12 (cons (wage 2) (hours->wages (rest (list 2 3))))) =… = (cons 12 (cons 24 (cons (wage 3) (hours->wages (rest (list 3)))))) =… = (cons 12 (cons 24 (cons 36 (hours->wages empty)))) =… = (cons 12 (cons 24 (cons 36 empty))) = (list 12 24 36) 51

「例題６．ステップ実行」の手順 1. 次を「定義用ウインドウ」で，実行しなさい • Intermediate Student で実行すること • 入力した後に，Execute ボタンを押す (define (hours->wages alon) (cond [(empty? alon) empty] [else (cons (wage (first alon)) (hours->wages (rest alon)))])) (define (wage h) (* 12 h)) (hours->wages (list 1 2 3)) 例題５ と同じ 2. DrScheme を使って，ステップ実行の様子を 確認しなさい （Step ボタン，Next ボタンを使用） • 理解しながら進むこと ☆ 次は，例題７に進んでください 52

(hours->wages (list 5 3 6)) から (list 60 36 72) が得られる過程の概略 (hours->wages (list 5 3 6)) 最初の式 = ... = (cons 60 (hours->wages (list 3 6))) =… = (cons 60 (cons 36 (hours->wages (list 6)))) =… = (cons 60 (cons 36 (cons 72 (hours->wages empty)))) = ... コンピュータ内部での計算 = (cons 60 (cons 36 (cons 72 empty))) 実行結果 53 = (list 60 36 72)

(hours->wages (list 5 3 6)) から (cons 60 (hours->wages (list 3 6)))が得られる過程 (hours->wages (list 5 3 6)) (hours->wages (list 5 3 6)) = (cond [(empty? (list 5 3 6)) empty] = ... この部分は [else (cons (wage (first (list 5 3 6))) = (cons 60 (hours->wages (list 3 6))) (hours->wages (rest (list 5 3 6))))]) = (cond [false empty] =… [else (cons (wage (first (list 5 3 6))) = (cons 60 (cons 36 (hours->wages (list 6)))) (hours->wages (rest (list 5 3 6))))]) = (cons (wage (first (list 5 3 6))) =… (hours->wages (rest (list 5 3 6)))) (wage 5) = (cons 60 (cons 36 (cons 72= (cons (hours->wages empty)))) (hours->wages (rest (list 5 3 6)))) = ... = (cons (* 12 5) (hours->wages (rest (list 5 3 6)))) = (cons 60 (cons 36 (cons 72= (cons empty))) 60 (hours->wages (rest (list 5 3 6)))) = (cons 60 (hours->wages (list 3 6))) 54 = (list 60 36 72)

(hours->wages (list 5 3 6)) から (cons 60 (hours->wages (list 3 6)))が得られる過程 (hours->wages (list 5 3 6)) (hours->wages (list 5 3 6)) = (cond [(empty? (list 5 3 6)) empty] = ... この部分は [else (cons (wage (first (list 5 3 6))) = (cons 60 (hours->wages (list 3 6))) (hours->wages (rest (list 5 3 6))))]) = (cond [false empty] =… これは， [else (cons (wage (first (list 5 3 6))) = (cons 60 (cons 36 (hours->wages (list 6)))) (hours->wages (rest (list 5 3 6))))]) (define (hours->wages alon) = (cons (wage (first (list 5 3 6))) = … (cond (hours->wages (rest (list 5 3 6)))) (wage 5) [(empty? = (cons 60 (cons 36alon) (consempty] 72= (cons (hours->wages empty)))) (hours->wages (rest (list 5 3 6)))) [else (cons (wage (first alon)) = ... = (cons (* 12 5) (hours->wages (rest alon)))])) (hours->wages (rest (list 5 3 6)))) = (cons 60 を (cons 72= (cons empty))) の alon (list36 5 3(cons 6) で置き換えたもの 60 (hours->wages (rest (list 5 3 6)))) = (cons 60 (hours->wages (list 3 6))) 55 = (list 60 36 72)

例題７．かけ算の表 • ２つの数 m, n から，m 行 n 列のかけ算の 表を出力するプログラム hyou を作り，実 行する • かけ算の表の「１行分」を出力する gyou も作 る • かけ算の表は，リストのリストの形で得る 56

「例題７．かけ算の表」の手順 1. 次を「定義用ウインドウ」で，実行しなさい • 入力した後に，Execute ボタンを押す ;; gyou: number -> list ;; a line representing products of two numbers ;; (hyou 3 4) = (list 12 9 6 3) (define (gyou m n) (cond [(= n 1) (cons m empty)] [else (cons (* m n) (gyou m (- n 1)))])) ;; hyou: number number -> list-of-list ;; table representing products of two numbers ;; (hyou 2 2) = (list (list 4 2) (list 2 1)) (define (hyou m n) (cond [(= m 0) empty] [else (cons (gyou m n) (hyou (- m 1) n))])) 2. その後，次を「実行用ウインドウ」で実行しなさい (hyou 3 4) ☆ 次は，例題８に進んでください 57

まず，Scheme のプログラムを コンピュータに読み込ませている 58

これは， (hyou 3 4) と書いて，m の値を 3, n の値を 4 に設定しての実行 実行結果である「(list (list 12 9 6 3) (list 8 6 4 2) (list 4 3 2 1))」が表示さ れる 59

入力と出力 (list (list 12 9 6 3) (list 8 6 4 2) (list 4 3 2 1)) 34 hyou 入力 入力は， ２つの数値 出力 出力はリストのリスト 60

;; gyou: number -> list ;; a line representing products of two numbers ;; (hyou 3 4) = (list 12 9 6 3) (define (gyou m n) (cond [(= n 1) (cons m empty)] [else (cons (* m n) (gyou m (- n 1)))])) ;; hyou: number number -> list-of-list ;; table representing products of two numbers ;; (hyou 2 2) = (list (list 4 2) (list 2 1)) (define (hyou m n) (cond [(= m 0) empty] [else (cons (gyou m n) (hyou (- m 1) n))])) 61

hyou, gyou の関係 • hyou • １つの表を作る 例） (list (list 12 9 6 3) (list 8 6 4 2) (list 4 3 2 1)) • gyou を使用 • gyou • １行分を作る 例） (list 12 9 6 3) 62

かけ算の表 hyou 1. 縦の数 m = 0 ならば： → 終了条件 empty → 自明な解 2. そうで無ければ： – １行分を作ることを m 回繰り返す 63

かけ算の表 hyou • hyou の内部に hyou が登場 (define (hyou m n) (cond [(= m 0) empty] [else (cons (gyou m n) (hyou (- m 1) n))])) • hyou の実行が繰り返される 例： (hyou 5 5) = (cons (list 25 20 15 10 5) (hyou 4 5)) (hyou 4 5) = (cons (list 20 16 12 8 4) (hyou 3 5)) ⇒ まさに「再帰」である 64

例題８．ステップ実行 • 関数 hyou （例題７）について，実行結果に 至る過程を見る • (gyou 3 4) から (list 12 6 9 3) に至る過程と， (hyou 5 5) から実行結果に至る過程を見る • DrScheme の stepper を使用する 65

「例題８．ステップ実行」の手順 (1/2) 次を「定義用ウインドウ」で，実行しなさい • Intermediate Student で実行すること • 入力した後に，Execute ボタンを押す ;; gyou: number -> list ;; a line representing products of two numbers ;; (hyou 3 4) = (list 12 9 6 3) (define (gyou m n) (cond [(= n 1) (cons m empty)] [else (cons (* m n) (gyou m (- n 1)))])) ;; hyou: number number -> list-of-list ;; table representing products of two numbers ;; (hyou 2 2) = (list (list 4 2) (list 2 1)) (define (hyou m n) (cond [(= m 0) empty] [else (cons (gyou m n) (hyou (- m 1) n))])) (gyou 3 4) 2. DrScheme を使って，ステップ実行の様子を 確認しなさい （Step ボタン，Next ボタンを使用） • 理解しながら進むこと 1. 例題７と同じ ☆ 次は，次ページに進んでください 66

「例題８．ステップ実行」の手順 (2/2) 次を「定義用ウインドウ」で，実行しなさい • Intermediate Student で実行すること • 入力した後に，Execute ボタンを押す ;; gyou: number -> list ;; a line representing products of two numbers ;; (hyou 3 4) = (list 12 9 6 3) (define (gyou m n) (cond [(= n 1) (cons m empty)] [else (cons (* m n) (gyou m (- n 1)))])) ;; hyou: number number -> list-of-list ;; table representing products of two numbers ;; (hyou 2 2) = (list (list 4 2) (list 2 1)) (define (hyou m n) (cond [(= m 0) empty] [else (cons (gyou m n) (hyou (- m 1) n))])) (hyou 5 5) 2. DrScheme を使って，ステップ実行の様子を 確認しなさい （Step ボタン，Next ボタンを使用） • 理解しながら進むこと 1. 例題７と同じ ☆ 次は，課題に進んでください 67

(gyou 3 4)から (list 12 9 6 3) が得られる過程の概略 (gyou 3 4) 最初の式 =… = (cons 12 (gyou 3 3)) =… = (cons 12 (cons 9 (gyou 3 2))) =… = (cons 12 (cons 9 (cons 6 (gyou 3 1)))) =… コンピュータ内部での計算 = (cons 12 (cons 9 (cons 6 (cons 3 empty)))) = (list 12 9 6 3) 実行結果 68

(gyou 3 4)から (cons (gyou 3 3)) が得られる過程 (gyou 3 4) (gyou 3 4) = (cond =… この部分は [(= 4 1) (cons 3 empty)] [else (cons (* 3 4) (gyou 3 (- 4 1)))]) = (cons 12 (gyou 3 3)) = (cond [false (cons 3 empty)] =… [else (cons (* 3 4) (gyou 3 (- 4 1)))]) = (cons 12 (cons 9 (gyou =3(cons 2))) (* 3 4) (gyou 3 (- 4 1))) = (cons 12 (gyou 3 (- 4 1))) =… = (cons 12 (gyou 3 3)) = (cons 12 (cons 9 (cons 6 (gyou 3 1)))) =… = (cons 12 (cons 9 (cons 6 (cons 3 empty)))) = (list 12 9 6 3) 69

(gyou 3 4)から (cons (gyou 3 3)) が得られる過程 (gyou 3 4) (gyou 3 4) = (cond =… この部分は [(= 4 1) (cons 3 empty)] [else (cons (* 3 4) (gyou 3 (- 4 1)))]) = (cons 12 (gyou 3 3)) = (cond [false (cons 3 empty)] =… [else (cons (* 3 4) (gyou 3 (- 4 1)))]) = これは， (cons 12 (cons 9 (gyou =3(cons 2))) (* 3 4) (gyou 3 (- 4 1))) = … (define (gyou m n) = (cons 12 (gyou 3 (- 4 1))) = (cons 12 (gyou 3 3)) (cond = (cons 12 (cons 9 (cons 6 (gyou 3 1)))) [(= n 1) (cons m empty)] =… [else (cons (* m6n)(cons (gyou3 m (- n 1)))])) = (cons 12 (cons 9 (cons empty)))) を936で，n を 4 で置き換えたもの =の (listm12 3) 70

(hyou 5 5)から 結果が得られる過程の概略 (hyou 5 5) 最初の式 =… = (cons (list 25 20 15 10 5) (hyou 4 5)) =… = (cons (list 25 20 15 10 5) (cons (list 20 16 12 8 4) (hyou 3 5))) =… = (cons (list 25 20 15 10 5) (cons (list 20 16 12 8 4) (cons (list 15 12 9 6 3) (hyou 2 5)))) =… = (cons (list 25 20 15 10 5) (cons (list 20 16 12 8 4) (cons (list 15 12 9 6 3) (cons (list 10 8 6 4 2) (hyou 1 5))))) =… = (cons (list 25 20 15 10 5) (cons (list 20 16 12 8 4) (cons (list 15 12 9 6 3) (cons (list 10 8 6 4 2) (cons (list 5 4 3 2 1) (cons (hyou 0 5)))))) =… = (cons (list 25 20 15 10 5) (cons (list 20 16 12 8 4) (cons (list 15 12 9 6 3) (cons (list 10 8 6 4 2) (cons (list 5 4 3 2 1) (cons empty))))) = (list (list 25 20 15 10 5) (list 20 16 12 8 4) (list 15 12 9 6 3) (list 10 8 6 4 2) (list 5 4 コンピュータ内部での計算 3 2 1)) 実行結果 71

7-3 課題 72

課題１ • 実行結果を報告しなさい • 「DrScheme の実行用ウインドウ」で実行して， 実行結果を報告しなさい (cons 1 (cons 2 (cons 3 empty))) 73

課題２ • 次の関数 insert について，「(insert 4 (list 5 1)) 」から「(list 5 4 1)」が得られる過程の概 略を数行程度で説明しなさい • DrScheme の stepper を使うと，すぐに分かる (define (insert n alon) (cond [(empty? alon) (cons n empty)] [else (cond [(<= (first alon) n) (cons n alon)] [(> (first alon) n) (cons (first alon) (insert n (rest alon)))])])) 74

課題２．リストと再帰の組み合わせ • 次の関数 insert について， ，「(relative-toabsolute (list 1 2 3))」 から 「(list 1 3 6)」が得ら れる過程の概略を数行程度で説明しなさい • DrScheme の stepper を使うと，すぐに分かる ;; relative-2-absolute : list-of-numbers -> list-of-numbers (define (relative-2-absolute alon) (cond [(empty? alon) empty] [else (cons (first alon) (add-to-each (first alon) (relative-2-absolute (rest alon))))])) ; ;; add-to-each : number (listof number) -> (listof number) (define (add-to-each n alon) (cond [(empty? alon) empty] [else (cons (+ (first alon) n) (add-to-each n (rest alon)))])) 75

課題３ 数値 n から，「1番目からn番目の奇数のリス ト」を作る関数 series-odd-list を作成し，実行 結果を報告しなさい • • 例えば，(series-odd-list 4) = (7 5 3 1) • ヒント： 次の空欄を埋めなさい (define (series-odd-list n) (cond [ [ ] ])) 76

課題４ • 関数 quadratic-roots （例題１）に関係するの 問題 • 二次方程式の係数 a, b, c から解の数 を求めるプログラム how-many を作成 し，実行結果を報告しなさい • 但し，a ≠0 とする 例えば (how-many 1 0 -1) = 2 (how-many 1 2 1) = 1 77

課題５．２次方程式の解 関数 quadratic-roots （例題１）についての問題 • • a =0 のときにも正しく計算ができるように書き直し を行い，書き直した結果と，実行結果を報告せよ a = 0 かつ b = 0 かつ c = 0 のとき すべての x が解である a = 0 かつ b = 0 かつ c ≠0 のとき 解なし a = 0 かつ b ≠ 0 のとき x=-c/b 78

課題６ ある年 y のある月 m のある日 d の曜日 youbi から，その「１週間分のリスト」を作る関数 を作成し，実行結果を報告しなさい • • youbi は 0 から 6 までの数値で， 0 なら日曜，1な ら月曜・・・ • 「１週間分のリスト」とは，日曜日から土曜日ま でのリストで，数値あるいは「'*」である 例えば ・ y = 2004, m = 10, d = 2, youbi = 6 のとき ⇒ 「(list '* '* '* '* '* 1 2)」 が出力される ・ y = 2004, m = 10, d = 31, youbi = 0 のとき ⇒ 「(list 31 '* '* '* '* '* '*)」 が出力される 79

課題７ ある年 y のある月 m から，その「月のカレン ダー」を作る関数を作成し，実行結果を報告 しなさい • • 「月のカレンダー」は，リストのリスト • １週間で１つのリストとなり，５週間あれば，５ つのリストからなる大きな１つのリスト 例えば (list (list '* '* '* '* 1 2 3) (list 4 5 6 7 8 9 10) (list 11 12 13 14 15 16 17) (list 18 19 20 21 22 23 24) (list 25 26 27 28 29 30 31)) 80

課題８ • ある年 y から，その「年のカレン ダー」を作る関数を作成し，実行 結果を報告しなさい • 「年のカレンダー」は，リストのリ ストのリスト 81

さらに勉強したい人への 補足説明事項 82

リストに関係する関数 • (append list ...) リストの連結 敢えて自分で書いてみた例を以下に紹介する 83

例題９．リストの連結 ２つのリスト（x と y）を連結する関数 myappend を作り，実行する • 1. x が空ならば： y 2. そうで無ければ： x の rest と y とを連結し，x の first と cons でつなげ る first rest x • y リストが空であるかどうかを調べるために empty? を使う 84

my-append 関数 (define (my-append x y) (cond [(empty? x) y] [else (cons (first x) (my-append (rest x) y))])) 85