Schemeで学ぶプログラミングの原理（授業資料）

環境構築：DrRacketのインストール

Schemeプログラミングの演習では、DrRacket（ドクター・ラケット）という統合開発環境（IDE: Integrated Development Environment、プログラムの作成・実行・デバッグを一つのソフトウェアで行える環境）を使用する。DrRacketは元々DrSchemeという名称であり、Scheme言語の学習用に開発された。2010年にPLT SchemeがRacketに改名された際、DrSchemeもDrRacketに改名された。

ダウンロードとインストール

1. 公式サイト https://racket-lang.org/download/ にアクセスする
2. 自分のOS（オペレーティングシステム）に対応したインストーラをダウンロードする（ダウンロードページで「Platform」から選択する）
3. ダウンロードしたファイルを実行し、画面の指示に従ってインストールする

OS別の起動方法

Windowsの場合、スタートメニューの「Racket」フォルダからDrRacketを起動する。スタートメニューで「DrRacket」と入力して検索することも可能である。

macOSの場合、Applicationsフォルダに配置したRacketフォルダ内のDrRacketアイコンをダブルクリックする。

Linux（Unix系OS）の場合、デスクトップ環境によってはDrRacketアイコンが作成される。コマンドラインからは、インストールディレクトリのbinサブディレクトリにあるdrracket実行ファイルを起動する。

Scheme言語の設定

DrRacketを起動した後、本講義で使用するScheme言語を設定する必要がある。

1. DrRacketを起動する
2. メニューから「Language」→「Choose Language...」を選択する
3. 「How to Design Programs」のセクションから適切な言語レベルを選択する（講義の指示に従う）
4. 「OK」をクリックし、「Run」ボタンを押して設定を反映する

動作確認

設定完了後、下部の対話エリア（Interactions）に以下を入力してEnterキーを押す。

(+ 1 2)

結果として「3」が表示されれば、環境構築は完了である。

推奨する参考資料

公式ドキュメントとして https://docs.racket-lang.org/getting-started/index.html（Getting Started）がある。初心者向けの導入として推奨される。

教科書として https://htdp.org/（How to Design Programs, Second Edition）がある。プログラム設計の体系的な方法論を学べる教科書であり、DrRacketとの連携を前提に書かれている。

日本語書籍としては、スライドに記載のとおり以下がある。

• R.ケント・ディヴィグ著、村上雅章訳『プログラミング言語SCHEME』ピアソン・エデュケーション、2000年
• ハロルド・エイブルソン、ジェラルド・ジェイ・サスマン、ジュリー・サスマン著、和田英一訳『計算機プログラムの構造と解釈 第2版』翔泳社、2014年（原著第2版1996年）

演習：パソコン演習の取り組み方を理解する

目的

Schemeプログラミングの演習に効果的に取り組むための学習サイクルを理解し、自律的な学習姿勢を身につける。

手順

1. スライド3〜4を読み、本講義の目標を確認する。「プログラムの実行イメージを持つ」とは、プログラムの指示に従ってコンピュータがどのように振る舞うかを頭の中で描けることを指す。
2. スライド5を読み、Schemeプログラミングで習得すべき6つのスキルを把握する。
   • 式、括弧の付け方、関数の書き方
   • 再帰（関数が自分自身を呼び出す手法）
   • リスト（複数のデータをまとめて扱うデータ構造）
   • 構造体（関連するデータを一つにまとめる仕組み）
   • プログラムの読解・作成能力
   • エラーの無いプログラムの作成能力
3. スライド8を読み、学習の流れを理解する。
   • 前半：説明資料で基本事項を理解する
   • 中盤：パソコン演習で例題を実行し、理解を深める
   • 後半：課題を解きながらプログラムに慣れる
4. スライド11を読み、演習への取り組み方5ステップを確認する。
   • 手本となるプログラムを良く読み、理解する
   • 手本をまねて、自分でプログラムを作ってみる
   • 動かしてみる
   • 動いたら、自分の納得のいくまで手を加える
   • 動かないようであれば、解決の糸口を自分で探してみる
5. スライド12を読み、課題への取り組み方を確認する。自分の実力にあった問題を選択し、確実に理解しながら解くことが重要である。
6. 上記「環境構築」の手順に従い、DrRacketをインストールして動作確認を行う。
7. 本ガイドの「推奨する参考資料」に記載したURLにアクセスし、どのような情報が得られるか確認する。

ヒント

参照

自己確認チェックリスト

本資料の学習を終えた後、以下の項目を自己確認する。

• DrRacketをインストールし、(+ 1 2) の実行結果として 3 が表示されることを確認した
• 「プログラムの実行イメージを持つ」とはどういうことか、自分の言葉で説明できる
• Schemeプログラミングで習得すべき6つのスキルを列挙できる
• 学習の3段階（説明資料→演習→課題）の流れを説明できる
• 演習への取り組み方5ステップを説明できる
• How to Design Programs（htdp.org）のWebサイトにアクセスできる

現行環境（Racket / DrRacket）についての注記

スライドで使用されている「DrScheme」は、2010年に「DrRacket」へと名称変更された。PLT Scheme プロジェクトが Racket へとリブランディングされたことに伴う変更である。現在の最新バージョンは Racket 9.0（2025年11月リリース）であり、公式サイト https://racket-lang.org/ から無償でダウンロードできる。

主な差異と対応

互換性

スライドに記載されている Scheme のプログラムおよび式は、DrRacket の Intermediate Student 言語設定においてそのまま動作する。define による関数定義、四則演算、sqrt、expt、remainder、quotient などの組み込み関数はすべて同様に使用できる。

演習環境の準備

DrSchemeの起動と設定

この設定により、ステップ実行機能（stepper）が使用可能になる。

例題1：実行結果に至る過程

目的

複合的な算術式がどのような順序で評価され、最終結果に至るかを理解する。括弧の内側が優先的に計算される規則を確認する。

手順

ヒント

例題2：関数のステップ実行

目的

関数呼び出し時に、関数本体がパラメータの実際の値で置き換わる過程を理解する。

手順

ヒント

例題3：2乗の和

目的

複数の関数を組み合わせてプログラムを構成する方法を学ぶ。一つの関数（sum-of-squares）が別の関数（sqr）を呼び出す構造を理解する。

手順

ヒント

例題4：ステップ実行（sum-of-squares）

目的

複数の関数が連携する場合の実行過程を追跡し、データの流れを理解する。

手順

ヒント

例題5：リングの面積

目的

実際の問題（リング状の図形の面積計算）を関数の組み合わせでモデル化する方法を学ぶ。

手順

ヒント

例題6：ステップ実行（area-of-ring）

目的

area-of-ring 関数の実行過程を追跡し、関数間のデータの流れを詳細に理解する。

手順

ヒント

例題7：利益の計算

目的

複数の関数が相互に連携する実践的なプログラムを作成する。ビジネスの利益計算モデルを関数で表現する方法を学ぶ。

背景知識

このプログラムは劇場の利益を計算するモデルである。

• 利益（profit）：収入 − 支出
• 収入（revenue）：観客数 × チケット代
• 支出（cost）：固定費 + 観客数 × 1人あたり費用
• 観客数（attendees）：チケット代に応じて変動する（チケット代が高いと観客数が減る）

手順

期待される結果

ヒント

例題8：ステップ実行（profit）

目的

4つの関数が連携するプログラムの実行過程を追跡し、複雑な関数呼び出しの流れを理解する。

手順

プログラム全体

例題7のプログラムに (profit 3) を追加した全体は以下のとおりである。

(define (profit ticket-price)
  (- (revenue ticket-price) (cost ticket-price)))

(define (revenue ticket-price)
  (* (attendees ticket-price) ticket-price))

(define (cost ticket-price)
  (+ 180 (* .04 (attendees ticket-price))))

(define (attendees ticket-price)
  (+ 120 (* (/ 15 .10) (- 5.00 ticket-price))))

(profit 3)

ヒント

課題1

目的

例題7で作成したプログラムを使い、異なるチケット代での利益を計算する。

手順

ヒント

課題2

目的

プログラムの一部を変更し、条件が変わった場合の結果を確認する。固定費がかからない場合の利益を計算する。

手順

ヒント

例題1：条件式

例題2：ステップ実行（interest-rate）

例題3：月の日数

例題4：ステップ実行（easy-get-num-of-days）

例題5：うるう年の判定

例題6：ステップ実行（is-leap?）

例題7：曜日を求める

課題1：重量に応じた料金計算

課題2：うるう年を考慮した月の日数

課題3：数式の計算

環境設定

演習を始める前に、DrSchemeを起動し、言語設定を「Intermediate Student」に変更する。

1. DrSchemeを起動する（プログラム → PLT Scheme → DrScheme）
2. Language → Choose Language → Intermediate Student を選択する
3. Executeボタンを押す

例題1：リストの式

目的

Schemeにおけるリストの基本的な記法を理解し、listキーワードを使ってリストを作成できるようになる。

手順

1. スライド4を確認し、リストが「データの並び」であり「順序がある」ことを理解する
2. スライド6を確認し、listキーワードの記法を確認する
3. 実行用ウインドウに以下の式を入力し、Enterキーを押して実行する

   (list 15 8 6 32 23)

4. 実行結果が (list 15 8 6 32 23) と表示されることを確認する

例題2：リストのfirstとrest

目的

リストの先頭要素を取得するfirstと、先頭を除いた残りを取得するrestの動作を理解する。

手順

1. スライド7を確認し、firstとrestの意味を理解する
2. 実行用ウインドウで以下の式を順に実行する

   (first (list 15 8 6 32 23))

   (rest (list 15 8 6 32 23))

3. firstの結果が 15（先頭要素）であることを確認する
4. restの結果が (list 8 6 32 23)（先頭を除いた残り）であることを確認する

例題3：リストのfirstとrest（要素が1つの場合）

目的

要素が1つしかないリストに対するfirst, restの動作と、空リストemptyの概念を理解する。

手順

1. スライド8を確認し、emptyの意味を理解する
2. 実行用ウインドウで以下の式を順に実行する

   (first (list 15))

   (rest (list 15))

3. firstの結果が 15 であることを確認する
4. restの結果が empty であることを確認する

例題4：append

目的

複数のリストを連結するappend関数の使い方を理解し、リストでない値を渡した場合のエラーを確認する。

手順

1. スライド17を確認し、appendの意味を理解する
2. 実行用ウインドウで以下の式を順に実行する

   (append (list 1 2) (list 3 4))

   (append (list 1 2) (list 3 4) (list 5 6))

   (append (list 1 2) 3 (list 4 5))

3. 最初の2つは正常に連結されることを確認する
4. 3つ目はエラーになることを確認し、その理由を考える

例題5：リストの基本操作

目的

firstとrestを組み合わせてリストの特定位置の要素を取得する関数を定義できるようになる。

手順

1. スライド47を確認し、「リストの3番目 ＝ リストのrestのrestのfirst」という関係を理解する
2. 定義用ウインドウに以下のプログラムを入力する

   (define (element3 a-list)
     (first (rest (rest a-list))))

3. Executeボタンを押してプログラムを読み込ませる
4. 実行用ウインドウで以下の式を実行する

   (element3 (list 1 2 3 4))

   (element3 (list 15 8 6 32 23))

5. 結果がそれぞれ 3、6 であることを確認する
6. 追加で (element3 (list 1 2)) を実行し、エラーになることを確認する

例題6：シンボル

目的

シンボル（symbol）の概念を理解し、cond文を使って条件に応じたシンボルを返す関数を作成できるようになる。

手順

1. スライド19を確認し、シンボルの記法（'を先頭につける）を理解する
2. 定義用ウインドウに以下のプログラムを入力する

   ;;judge: number -> symbol
   (define (judge x)
     (cond
       [(<= x 20) 'Cold]
       [(and (< 20 x) (<= x 30)) 'Warm]
       [(< 30 x) 'Hot]))

3. Executeボタンを押す
4. 実行用ウインドウで以下の式を実行する

   (judge 15)

   (judge 20)

   (judge 25)

5. 結果がそれぞれ 'Cold、'Cold、'Warm であることを確認する

例題7：数字かシンボルを出力

目的

条件に応じて異なる型（数値またはシンボル）の値を返す関数を作成できるようになる。cond文のelse節の使い方を理解する。

手順

1. 定義用ウインドウに以下のプログラムを入力する

   (define (ast x)
     (cond
       [(> x 0) x]
       [else '*]))

2. Executeボタンを押す
3. 実行用ウインドウで以下の式を実行する

   (ast 10)

   (ast 0)

   (ast -10)

4. 結果がそれぞれ 10、'*、'* であることを確認する

例題8：シンボル（シンボルの比較）

目的

symbol=?を使ったシンボルの比較方法を理解し、シンボルを入力として受け取りシンボルを返す関数を作成できるようになる。

手順

1. スライド20を確認し、symbol=?の使い方を理解する
2. 定義用ウインドウに以下のプログラムを入力する

   ;;reply: symbol -> symbol
   ;;to determine a reply for the greeting s
   (define (reply s)
     (cond
       [(symbol=? 'GoodMorning s) 'Hi]
       [(symbol=? 'HowAreYou s) 'Fine]
       [(symbol=? 'GoodAfternoon s) 'NeedANap]
       [(symbol=? 'GoodEvening s) 'BoyAmITired]))

3. Executeボタンを押す
4. 実行用ウインドウで以下の式を実行する

   (reply 'GoodMorning)

   (reply 'Hello)

5. 最初の結果が 'Hi であることを確認する
6. 2番目がエラーになることを確認し、その理由を考える

課題1：リスト操作の実行結果

目的

list, first, restの動作を様々なケースで確認し、実行結果を正確に予測できるようになる。

手順

1. 以下の表の各セルについて、実行結果を予測する
2. 実行用ウインドウで実際に実行し、予測と比較する
3. エラーが発生する場合は「エラー」と記録する

課題2：真夏日・冬日判定関数

目的

複数の引数を受け取り、複数の条件を判定して適切な文字列を返す関数を設計・実装できるようになる。

手順

1. 以下の判定基準を確認する
   • "Tropical Day"（真夏日）：1日の最高気温が30度以上
   • "Summer Day"（夏日）：1日の最高気温が25度以上
   • "Frost Day"（冬日）：1日の最低気温が0度未満
   • "Ice Day"（真冬日）：1日の最高気温が0度未満
2. 関数summer-winter-dayの仕様を考える
   • 入力：high（最高気温）、low（最低気温）
   • 出力：上記のいずれかの文字列
3. 条件の優先順位を検討する（複数の条件に該当する場合どれを返すか）
4. 定義用ウインドウでプログラムを作成する
5. 様々な入力値で実行し、正しく判定されることを確認する

課題3：日付存在判定関数

目的

複雑な条件分岐（月ごとの日数、閏年判定など）を含む関数を設計・実装できるようになる。

手順

1. 日付の有効性判定に必要な条件を整理する
   • 月ごとの日数の違い（28日、30日、31日）
   • 閏年の判定（2月の日数が変わる）
   • 日が1以上であること
2. 関数の仕様を考える
   • 入力：y（年）、m（月）、d（日）
   • 出力：日付が存在すればdを、存在しなければシンボル'*を返す
3. 例題7のast関数の構造を参考に、条件分岐を設計する
4. 定義用ウインドウでプログラムを作成する
5. 以下のテストケースで動作を確認する
   • (関数名 2004 10 10) → 10
   • (関数名 2004 10 0) → '*
   • (関数名 2004 10 32) → '*

環境設定

演習を始める前に、DrSchemeを以下の手順で設定する。

1. DrSchemeを起動する（プログラム → PLT Scheme → DrScheme）
2. 言語設定を「Intermediate Student」に変更する
   • Language → Choose Language → Intermediate Student を選択
   • Execute ボタンを押して設定を反映する

例題1：リストの総和

目的

再帰を用いてリストの全要素の総和を求める関数を作成し、再帰関数の基本構造を理解する。

手順

1. 定義用ウインドウに以下のコードを入力する

(define (list-sum a-list)
  (cond
    [(empty? a-list) 0]
    [else (+ (first a-list) (list-sum (rest a-list)))]))

2. Execute ボタンを押してプログラムを読み込む
3. 実行用ウインドウで以下を実行し、結果を確認する

(list-sum (list 1 2 3))
(list-sum (list 11 12 13))

例題2：ステップ実行（list-sum）

目的

DrSchemeのstepper機能を使い、再帰関数の計算過程を段階的に追跡する方法を習得する。

手順

1. 定義用ウインドウに例題1のコードと実行文を入力する

(define (list-sum a-list)
  (cond
    [(empty? a-list) 0]
    [else (+ (first a-list) (list-sum (rest a-list)))]))
(list-sum (list 1 2 3))

2. Step ボタンを押してステップ実行を開始する
3. Next ボタンを押しながら、各ステップで式がどのように変換されるかを観察する
4. 以下の展開過程を実際の画面で確認する
   • (list-sum (list 1 2 3)) から (+ 1 (list-sum (list 2 3))) への展開
   • 最終的に (+ 1 (+ 2 (+ 3 0))) となり 6 が得られる過程

例題3：平均点

目的

既存の関数を組み合わせて新しい関数を定義する方法を学ぶ。総和を求める関数と要素数を求める関数を利用して平均を計算する。

手順

1. 定義用ウインドウに以下のコードを入力する

;; list-sum: list -> number
;; total of a list
;; (list-sum (list 40 90 80)) = 210
(define (list-sum a-list)
  (cond
    [(empty? a-list) 0]
    [else (+ (first a-list) (list-sum (rest a-list)))]))

;; average: list -> number
;; average of a list
;; (average (list 40 90 80)) = 70
(define (average a-list)
  (/ (list-sum a-list) (length a-list)))

2. Execute ボタンを押す
3. 実行用ウインドウで以下を実行する

(average (list 40 90 80))
(average (list 100 200 300 400 500))

例題4：ステップ実行（average）

目的

複数の関数が組み合わされた場合の計算過程を追跡し、関数呼び出しの評価順序を理解する。

手順

1. 定義用ウインドウに例題3のコードと実行文を入力する

;; （例題3のコードに加えて）
(average (list 40 90 80))

2. Step ボタンとNext ボタンを使ってステップ実行する
3. 以下の過程を確認する
   • (average (list 40 90 80)) が (/ (list-sum ...) (length ...)) に展開される
   • list-sum の計算が先に進み、210 が得られる
   • length の計算で 3 が得られる
   • 最終的に (/ 210 3) が 70 になる

例題5：「5」を含むか調べる

目的

リスト内に特定の値が存在するかを判定する関数を作成し、真偽値（true/false）を返す再帰関数の書き方を学ぶ。

手順

1. 定義用ウインドウに以下のコードを入力する

;; contains-5?: list -> true or false
;; it investigates whether 5 is included
;; (contains-5? (list 3 5 7 9)) = true
(define (contains-5? a-list)
  (cond
    [(empty? a-list) false]
    [else (cond
            [(= (first a-list) 5) true]
            [else (contains-5? (rest a-list))])]))

2. Execute ボタンを押す
3. 実行用ウインドウで以下を実行する

(contains-5? (list 1 2 3 4))
(contains-5? (list 3 5 7 9))

例題6：ステップ実行（contains-5?）

目的

条件分岐を含む再帰関数の計算過程を追跡し、早期終了（5が見つかった時点で探索を打ち切る）の仕組みを理解する。

手順

1. 定義用ウインドウに例題5のコードと実行文を入力する

;; （例題5のコードに加えて）
(contains-5? (list 3 5 7 9))

2. Step ボタンとNext ボタンを使ってステップ実行する
3. 以下の過程を確認する
   • 先頭の3は5ではないので、rest である (list 5 7 9) を調べる
   • 先頭の5が見つかり、true が返される
   • (list 7 9) は調べられない

例題7：ベクトルの内積

目的

2つのリストを同時に処理する再帰関数を作成し、複数パラメータを扱う再帰の書き方を学ぶ。

手順

1. 定義用ウインドウに以下のコードを入力する

;; product: list list -> number
;; inner product of two vectors
;; (product (list 1 2 3) (list 4 5 6)) = 32
(define (product x y)
  (cond
    [(empty? x) 0]
    [else (+ (* (first x) (first y))
             (product (rest x) (rest y)))]))

2. Execute ボタンを押す
3. 実行用ウインドウで以下を実行する

(product (list 1 2 3) (list 4 5 6))

例題8：ステップ実行（product）

目的

2つのリストを同時に処理する再帰の計算過程を追跡し、両方のリストが同時に縮小していく様子を確認する。

手順

1. 定義用ウインドウに例題7のコードと実行文を入力する

;; （例題7のコードに加えて）
(product (list 1 2 3) (list 4 5 6))

2. Step ボタンとNext ボタンを使ってステップ実行する
3. 以下の過程を確認する
   • (product (list 1 2 3) (list 4 5 6)) から (+ 4 (product (list 2 3) (list 5 6))) への展開
   • 最終的に (+ 4 (+ 10 (+ 18 0))) となり 32 が得られる

課題1：list-sum の計算過程の説明

目的

再帰関数の動作を言葉で説明できるようになり、計算過程の理解を深める。

手順

1. DrScheme で例題2のステップ実行を再度行う
2. (list-sum (list 1 2 3)) から 6 が得られる過程を観察する
3. 数行程度（3〜5行）で計算過程を説明する文章を作成する

課題2：実行エラーの解決

目的

stepper を使ってエラーの原因を特定する方法を習得し、デバッグ（プログラムの誤りを発見・修正すること）の技術を身につける。

手順

1. 定義用ウインドウに以下のコードを入力する

(define (list-length a-list)
  (cond
    [(empty? a-list) 0]
    [else (+ 1 (list-length (rest a-list)))]))
(list-length 100)

2. Execute ボタンを押す（赤い文字でエラーメッセージが表示される）
3. Step ボタンを押してステップ実行を開始する
4. エラーが発生する箇所まで Next ボタンで進む
5. エラーの原因を特定し、報告を作成する

課題3：シンボル出現の判定プログラム

目的

contains-5? を一般化し、任意のシンボルを検索できる関数を作成する。

手順

1. contains-5? の構造を確認する（スライド45）
2. 以下の仕様を満たす関数 contains? を設計する
   • 入力：シンボルのリスト a-list、検索対象のシンボル a-symbol
   • 出力：a-list が a-symbol を含むとき true、含まないとき false
3. 設計した関数を実装し、テストする

(symbol=? 'apple 'apple)  ; → true
(symbol=? 'apple 'orange) ; → false

課題4：偶数を含むか調べる

目的

述語関数（predicate、真偽値を返す関数）を活用した判定処理を実装する。

手順

1. contains-5? の構造を確認する
2. 「先頭要素が5か」を判定している部分を「先頭要素が偶数か」に変更する方針で設計する
3. 偶数の判定には組み込み関数 even? を使用する
4. 設計した関数を実装し、様々なリストでテストする

課題5：Horner法による多項式計算

目的

数学的なアルゴリズムをプログラムとして実装する経験を積む。Horner法（多項式を効率的に計算する手法）を用いた再帰関数を作成する。

手順

1. スライド79-80でHorner法のアルゴリズムを理解する
2. 多項式 f(x) = a₀ + a₁x + a₂x² + ... + aₙxⁿ をHorner法で書き換えると f(x) = a₀ + x(a₁ + x(a₂ + ... + x(aₙ₋₁ + xaₙ)...)) となることを確認する
3. 係数のリスト（a₀から aₙ の順）と x の値を受け取り、f(x) を計算する関数を設計する
4. 設計した関数を実装し、テストする

正解例

以下に、係数リストを高次から低次の順（aₙ, aₙ₋₁, ..., a₁, a₀）で渡す設計の実装例を示す。

;; horner: list number -> number
;; Horner法による多項式の計算
;; 係数リストは高次から低次の順（例：3x² + 6x + 5 なら (list 3 6 5)）
;; (horner (list 3 6 5) 2) = 29
(define (horner coeffs x)
  (cond
    [(empty? coeffs) 0]
    [else (+ (first coeffs)
             (* x (horner (rest coeffs) x)))]))

この関数の動作を説明する。係数リスト (list 3 6 5) と x = 2 を与えた場合、以下のように計算が進む。

1. (horner (list 3 6 5) 2) は (+ 3 (* 2 (horner (list 6 5) 2))) に展開される
2. (horner (list 6 5) 2) は (+ 6 (* 2 (horner (list 5) 2))) に展開される
3. (horner (list 5) 2) は (+ 5 (* 2 (horner empty 2))) に展開される
4. (horner empty 2) は終了条件により 0 を返す
5. 逆順に計算すると、(+ 5 (* 2 0)) = 5、(+ 6 (* 2 5)) = 16、(+ 3 (* 2 16)) = 35

上記の計算結果 35 は、3×2² + 6×2 + 5 = 12 + 12 + 5 = 29 と一致しない。これは、上記の実装が Horner 法の計算順序と異なるためである。正しい Horner 法の実装には、アキュムレータ（累積変数）を用いる方法がある。

;; horner: list number -> number
;; Horner法による多項式の計算（アキュムレータ使用）
;; 係数リストは高次から低次の順（例：3x² + 6x + 5 なら (list 3 6 5)）
;; (horner (list 3 6 5) 2) = 29
(define (horner coeffs x)
  (horner-acc coeffs x 0))

;; horner-acc: list number number -> number
;; アキュムレータを用いた補助関数
(define (horner-acc coeffs x acc)
  (cond
    [(empty? coeffs) acc]
    [else (horner-acc (rest coeffs) x (+ (first coeffs) (* acc x)))]))

この実装では、アキュムレータ acc に計算途中の値を保持しながら処理を進める。係数リスト (list 3 6 5) と x = 2 を与えた場合の計算過程は以下のとおりである。

1. (horner-acc (list 3 6 5) 2 0)：acc = 0 + 3×0 ではなく、acc = 0、first = 3 より、新しい acc = 3 + 0×2 = 3
2. (horner-acc (list 6 5) 2 3)：新しい acc = 6 + 3×2 = 12
3. (horner-acc (list 5) 2 12)：新しい acc = 5 + 12×2 = 29
4. (horner-acc empty 2 29)：終了条件により 29 を返す

実行例を以下に示す。

(horner (list 3 6 5) 2)  ; → 29  （3x² + 6x + 5 で x = 2）
(horner (list 1 0 0) 3)  ; → 9   （x² で x = 3）
(horner (list 1 1 1 1) 2) ; → 15 （x³ + x² + x + 1 で x = 2）

補足：さらに学びたい人へ

スライド81-119には、リストの長さを求める my-length 関数と、n番目の要素を取得する my-list-ref 関数の実装例が掲載されている。これらは組み込み関数 length と list-ref と同等の機能を持つ関数を自作したものである。再帰の理解をさらに深めたい場合は、これらの例も学習するとよい。

第1部：基礎知識の確認

演習を始める前に、以下の基礎知識をスライドで確認する。

リストの表記方法

Schemeではリストを2種類の方法で表記できる。

cons形式：(cons 'x (cons 'y (cons 'z empty)))のように、consを連ねて記述する方式。emptyは空リストを意味し、リストの末尾を示す。

list形式：(list 'x 'y 'z)のように、listを使って直接記述する方式。

両者は同じリストを表現する。consはリストのfirst（先頭要素）とrest（残りのリスト）をつなげてリストを構築する操作である。

第2部：例題演習

例題1：2次方程式

目的

2次方程式の解を求める関数を作成し、条件分岐（cond）を用いて解の個数に応じた出力を行う方法を学ぶ。

手順

(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)))]))

(quadratic-roots 1 -5 6)
(quadratic-roots 2 0 -1)
(quadratic-roots 1 2 1)
(quadratic-roots 1 0 1)

例題2：リストの生成

目的

再帰（関数が自分自身を呼び出す構造）を用いて、指定した個数の要素からなるリストを生成する方法を学ぶ。

手順

(define (1list n)
  (cond
    [(= n 0) empty]
    [else (cons 1 (1list (- n 1)))]))

(1list 0)
(1list 3)

例題3：ステップ実行

目的

DrSchemeのstepper機能を使い、再帰関数の実行過程を視覚的に追跡する方法を学ぶ。

手順

(define (1list n)
  (cond
    [(= n 0) empty]
    [else (cons 1 (1list (- n 1)))]))

(1list 3)

例題4：リストの生成

目的

例題2と同様の再帰パターンを用いて、シンボルを要素とするリストを生成する。数値以外の要素でも同じ手法が適用できることを確認する。

手順

(define (astlist n)
  (cond
    [(= n 0) empty]
    [else (cons '* (astlist (- n 1)))]))

(astlist 0)
(astlist 3)
(astlist 10)

例題5：賃金リストの生成

目的

入力リストの各要素に対して関数を適用し、結果を新しいリストとして生成する方法を学ぶ。これはリスト処理の基本パターンの一つである。

手順

(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 5 3 6))
(hours->wages (list 100 200 300 400))
(hours->wages empty)

例題6：ステップ実行

目的

hours->wages関数の実行過程をステップ実行で追跡し、リスト処理の再帰パターンの動作を詳細に理解する。

手順

(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))

例題7：かけ算の表

目的

リストのリスト（入れ子構造）を生成する方法を学ぶ。複数の関数を組み合わせて複雑なデータ構造を構築する手法を理解する。

手順

;; gyou: number number -> list
;; 1行分（m × n, m × (n-1), ..., m × 1）を生成
(define (gyou m n)
  (cond
    [(= n 1) (cons m empty)]
    [else (cons (* m n) (gyou m (- n 1)))]))

;; hyou: number number -> list-of-list
;; m行n列のかけ算の表を生成
(define (hyou m n)
  (cond
    [(= m 0) empty]
    [else (cons (gyou m n) (hyou (- m 1) n))]))

(hyou 3 4)

例題8：ステップ実行

目的

gyou関数とhyou関数の実行過程をステップ実行で追跡し、入れ子構造のリストがどのように構築されるかを理解する。

手順

(define (gyou m n)
  (cond
    [(= n 1) (cons m empty)]
    [else (cons (* m n) (gyou m (- n 1)))]))

(define (hyou m n)
  (cond
    [(= m 0) empty]
    [else (cons (gyou m n) (hyou (- m 1) n))]))

(gyou 3 4)

第3部：課題演習

課題1

目的

cons形式でのリスト記述が、どのようなlist形式の結果になるかを確認する。

手順

(cons 1 (cons 2 (cons 3 empty)))

課題2

目的

与えられた関数の実行過程を分析し、再帰の動作を説明する能力を養う。

手順（問題1）

(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)))])]))

(insert 4 (list 5 1))

手順（問題2）

(define (relative-2-absolute alon)
  (cond
    [(empty? alon) empty]
    [else (cons (first alon)
                (add-to-each (first alon)
                             (relative-2-absolute (rest alon))))]))

(define (add-to-each n alon)
  (cond
    [(empty? alon) empty]
    [else (cons (+ (first alon) n)
                (add-to-each n (rest alon)))]))

(relative-2-absolute (list 1 2 3))

課題3

目的

例題2・4で学んだ再帰パターンを応用し、奇数の列を生成する関数を自力で作成する。

手順

(define (series-odd-list n)
  (cond
    [ ]
    [ ]))

(series-odd-list 4)

課題4

目的

例題1の関数を基に、解の個数を返す関数を作成する。条件分岐の応用を練習する。

手順

(how-many 1 0 -1)
(how-many 1 2 1)

課題5

目的

例題1の関数を拡張し、より多くの場合に対応できるようにする。条件分岐の設計を練習する。

手順

課題6

目的

日付と曜日の情報から1週間分のカレンダー行を生成する。リスト生成と条件分岐を組み合わせた応用問題である。

アルゴリズムの概要

1週間分のカレンダー行を生成するには、以下の手順を踏む。

手順

正解プログラム

;; うるう年判定
(define (leap-year? y)
  (or (and (= (remainder y 4) 0)
           (not (= (remainder y 100) 0)))
      (= (remainder y 400) 0)))

;; 月の日数を返す
(define (days-in-month y m)
  (cond
    [(= m 2) (if (leap-year? y) 29 28)]
    [(or (= m 4) (= m 6) (= m 9) (= m 11)) 30]
    [else 31]))

;; 1週間分のリストを生成（補助関数）
(define (week-list y m start-day pos)
  (cond
    [(= pos 7) empty]
    [else
     (let ([day (+ start-day pos)])
       (cons (if (and (>= day 1) (<= day (days-in-month y m)))
                 day
                 '*)
             (week-list y m start-day (+ pos 1))))]))

;; 1週間分のリストを生成（メイン関数）
(define (one-week y m d youbi)
  (week-list y m (- d youbi) 0))

課題7

目的

課題6を発展させ、1か月分のカレンダーを生成する。リストのリストを生成する手法（例題7で学習）を応用する。

アルゴリズムの概要

月のカレンダーを生成するには、以下の手順を踏む。

Zellerの公式は、年月日から曜日を計算する公式である。1月と2月は前年の13月、14月として扱う。

手順

正解プログラム

;; Zellerの公式による曜日計算（0=日曜、1=月曜、...、6=土曜）
(define (zeller y m d)
  (let* ([adjusted-m (if (< m 3) (+ m 12) m)]
         [adjusted-y (if (< m 3) (- y 1) y)]
         [q d]
         [k (remainder adjusted-y 100)]
         [j (quotient adjusted-y 100)]
         [h (remainder (+ q
                          (quotient (* 13 (+ adjusted-m 1)) 5)
                          k
                          (quotient k 4)
                          (quotient j 4)
                          (* -2 j))
                       7)])
    (remainder (+ h 6) 7)))

;; 月カレンダー生成（補助関数）
(define (month-calendar-helper y m current-day)
  (cond
    [(> current-day (days-in-month y m)) empty]
    [else
     (let* ([youbi (zeller y m current-day)]
            [week (one-week y m current-day youbi)]
            [next-day (+ current-day (- 7 youbi))])
       (cons week (month-calendar-helper y m next-day)))]))

;; 月カレンダー生成（メイン関数）
(define (month-calendar y m)
  (month-calendar-helper y m 1))

課題8

目的

課題7をさらに発展させ、1年分のカレンダーを生成する。リストのリストのリストという3重の入れ子構造を扱う。

アルゴリズムの概要

年のカレンダーを生成するには、以下の手順を踏む。

手順

正解プログラム

;; 年カレンダー生成（補助関数）
(define (year-calendar-helper y m)
  (cond
    [(> m 12) empty]
    [else (cons (month-calendar y m)
                (year-calendar-helper y (+ m 1)))]))

;; 年カレンダー生成（メイン関数）
(define (year-calendar y)
  (year-calendar-helper y 1))

補足：リストの連結

例題9として、2つのリストを連結する関数my-appendが紹介されている。標準関数appendの動作を自作することで、リスト操作の理解を深めることができる。

例題1：条件式

手順

1. DrSchemeを起動する。メニューから「Language → Choose Language → Intermediate Student」を選択し、Executeボタンを押す。
2. スライド27のグラフを確認し、残高と利率の対応関係を把握する。残高が1000以下なら4%、5000以下なら4.5%、5000より多ければ5%である。
3. 以下のプログラムを定義ウィンドウに入力する。

   ;; interest-rate: number -> number
   ;; to determine the interest rate
   ;; for the given amount
   (define (interest-rate amount)
     (cond
       [(<= amount 1000) 0.040]
       [(<= amount 5000) 0.045]
       [(> amount 5000) 0.050]))

4. Executeボタンを押してプログラムを読み込ませる。
5. 対話ウィンドウで以下のテストケースを実行し、期待値と一致するか確認する。
   • (interest-rate 500) → 期待値: 0.040
   • (interest-rate 1000) → 期待値: 0.040
   • (interest-rate 1500) → 期待値: 0.045
   • (interest-rate 5000) → 期待値: 0.045
   • (interest-rate 10000) → 期待値: 0.050
6. 境界値（1000, 5000）での動作を確認し、条件式の評価順序を理解する。

課題1：関数fの実行結果

手順

1. DrSchemeを起動し、Intermediate Studentモードに設定する。
2. 以下の関数fの定義を入力する。

   (define (f n)
     (* n 20))

3. Executeボタンを押してプログラムを読み込ませる。
4. 対話ウィンドウで(f 5 20)を実行する。
5. 表示されるエラーメッセージを確認し、その原因を考察する。
6. 関数fの定義（引数の個数）と、呼び出し時に渡した引数の個数を比較する。
7. 考察結果を文章でまとめる。

課題2：エラーの原因説明

手順

1. DrSchemeを起動し、Intermediate Studentモードに設定する。
2. 以下の6つのScheme式を、1つずつ入力して実行する。
3. 各式について、以下の手順で分析する。
   • エラーメッセージを確認する
   • エラーの種類（構文エラーまたは実行エラー）を判定する
   • エラーの原因を特定する
4. 分析結果を、式ごとに以下の形式でまとめる。
   • 式の内容
   • エラーの種類
   • 原因の説明

各式の分析観点

論理的エラーについて

論理的エラー（Logical Errors）は、構文エラーや実行エラーとは異なり、プログラムが正常に実行され結果を出力するが、その結果が誤っているという種類のエラーである。DrSchemeはこのエラーを自動的に検出できないため、プログラマ自身が発見しなければならない。

論理的エラーの例

例1：三角形の面積計算の誤り

(define (area-of-triangle b h)
  (+ b h))

誤りの内容：底辺bと高さhを足し算している。三角形の面積は「底辺×高さ÷2」であるため、正しくは(/ (* b h) 2)または(* 0.5 (* b h))とすべきである。

例2：時給計算の誤り

(define (wage h)
  (+ 12 h))

誤りの内容：時給12に労働時間hを足し算している。賃金は「時給×労働時間」であるため、正しくは(* 12 h)とすべきである。

例3：リングの面積計算で内外を逆にした誤り

(define (area-of-ring outer inner)
  (- (area-of-disk inner) (area-of-disk outer)))

誤りの内容：内側の円の面積から外側の円の面積を引いている。外側が大きいため、結果が負の値になる。正しくは(- (area-of-disk outer) (area-of-disk inner))とすべきである。

論理的エラーへの対処方針

論理的エラーは構文的に正しく、実行も完了するため、発見が困難である。以下の方法で対処する。

1. Exampleの活用：プログラム設計法のExample段階で、事前に期待される入出力を明確にしておき、実行結果と照合する。
2. 境界値のテスト：特殊なケース（0、負数、最大値など）でテストを行い、異常な結果が出ないか確認する。
3. 手計算との照合：小さな入力値で手計算した結果と、プログラムの出力を比較する。

補足：プログラム設計法（Design Recipe）の実践

本演習では直接の課題として指定されていないが、プログラム設計法を、例題1や自作の関数に適用して練習することを推奨する。

設計法の5段階は以下のとおりである。

1. Contract：関数名、入力の型、出力の型を定義する
2. Purpose：関数が何をするかを文章で記述する
3. Example：具体的な入出力の例を示す
4. Definition：関数本体を作成する
5. Test：Exampleで示した例を実行し、期待値と一致するか確認する

学習の到達目標

本演習を完了すると、以下のことができるようになる。

• 高階関数（関数を引数として受け取る関数）のプログラムを理解し実行できる
• reduce、series、taylor-seriesの各関数の動作を説明できる
• テーラー展開を用いて数学関数の近似値を計算できる

環境設定

DrSchemeを起動し、Language設定を「Advanced Student」に変更する。手順は以下のとおりである。

Advanced Studentモードは高階関数の実行に必要である。

例題1：リストの総和

目的

高階関数reduce（関数を引数として受け取り、リストの要素を順次処理する関数）の動作を理解し、これを利用してリストの総和を求める関数list-sumを作成する。

手順

コード

;; reduce: (number data -> data) data list -> data
;; (reduce g 0 (list 1 2 3)) = (g 1 (g 2 (g 3 0)))
(define (reduce op base L)
  (cond
    [(empty? L) base]
    [else (op (first L) (reduce op base (rest L)))]))

;; list-sum: list -> number
;; total of a list
;; (list-sum (list 40 90 80)) = 210
(define (list-sum a-list)
  (reduce + 0 a-list))

例題2：xのn乗の近似値

目的

#iを付けた近似計算の動作を理解する。Schemeでは#iを数値に付けると、その計算は近似値（浮動小数点数）として処理される。

手順

例題3：数列の和

目的

高階関数seriesを使用して、数列の和 Σf(k)（k=1からn）を計算する方法を理解する。

手順

コード

;; series: number (number -> number) -> number
;; (series f2 3) = (+ (f2 3) (+ (f2 2) (+ (f2 1))))
(define (series n f)
  (cond
    [(= n 1) (f 1)]
    [else (+ (f n) (series (- n 1) f))]))

(define (f2 k) (* k k))
(define (f3 k) (* k k k))

例題4：数列の和のリスト

目的

series-iter関数を使用して、数列の部分和のリストを作成する。これにより、級数の収束の様子を観察できる。

手順

コード

;; series: number (number -> number) -> number
;; (series f2 3) = (+ (f2 3) (+ (f2 2) (+ (f2 1))))
(define (series n f)
  (cond
    [(= n 1) (f 1)]
    [else (+ (f n) (series (- n 1) f))]))

;; series-iter : number (number -> number) -> list
(define (series-iter n f)
  (cond
    [(= n 0) empty]
    [else (cons (series n f) (series-iter (- n 1) f))]))

(define (f4 k) (/ 1 (* k k)))

例題5：べき級数

目的

高階関数taylor-seriesを使用して、べき級数 Σg(k)·x^k（k=0からn）を計算する方法を理解する。

手順

コード

;; taylor-series: number number (number -> number)
;;                -> number
;; (taylor-series 2 3 g) =
;;   (+ (* (g 3) (expt 2 3)
;;      (+ (* (g 2) (expt 2 2))
;;         (+ (* (g 1) (expt 2 1))
;;            (g 0))))
(define (taylor-series x n g)
  (cond
    [(= n 0) (g 0)]
    [else (+ (* (g n) (expt x n))
             (taylor-series x (- n 1) g))]))

(define (g1 k) k)

例題6：指数関数のテーラー展開

目的

taylor-series関数を使用して、指数関数e^xのテーラー展開による近似値を計算する。

手順

コード

;; taylor-series: number number (number -> number)
;;                -> number
(define (taylor-series x n g)
  (cond
    [(= n 0) (g 0)]
    [else (+ (* (g n) (expt x n))
             (taylor-series x (- n 1) g))]))

(define (factorial k)
  (cond
    [(= k 0) 1]
    [else (* k (factorial (- k 1)))]))

(define (exp-term k) (/ 1 (factorial k)))

(define (my-exp x)
  (taylor-series x 20 exp-term))

例題7：cos関数のテーラー展開

目的

taylor-series関数を使用して、cos関数のテーラー展開による近似値を計算する。

手順

コード

;; taylor-series: number number (number -> number)
;;                -> number
(define (taylor-series x n g)
  (cond
    [(= n 0) (g 0)]
    [else (+ (* (g n) (expt x n))
             (taylor-series x (- n 1) g))]))

(define (factorial k)
  (cond
    [(= k 0) 1]
    [else (* k (factorial (- k 1)))]))

(define (cos-term k)
  (cond
    [(odd? k) 0]
    [else (cond
            [(= (remainder k 4) 0) (/ 1 (factorial k))]
            [else (/ -1 (factorial k))])]))

(define (my-cos x)
  (taylor-series x 20 cos-term))

例題8：対数関数のテーラー展開

目的

taylor-series関数を使用して、対数関数log(1+x)のテーラー展開による近似値を計算する。

手順

コード

;; taylor-series: number number (number -> number)
;;                -> number
(define (taylor-series x n g)
  (cond
    [(= n 0) (g 0)]
    [else (+ (* (g n) (expt x n))
             (taylor-series x (- n 1) g))]))

(define (log-term k)
  (cond
    [(= k 0) 0]
    [else (/ (expt -1 (- k 1)) k)]))

(define (my-log x)
  (taylor-series (- x 1) 20 log-term))

課題1：近似計算の理解

目的

#i記号と指数表記の意味を正確に理解し、近似計算と厳密計算の違いを説明できるようになる。

手順

課題2：my-expの理解

目的

テーラー展開の部分和を段階的に計算することで、級数の収束過程を理解する。

手順

課題3：数列の和の列1

目的

series-iter関数を使用して交代級数（正負の項が交互に現れる級数）の部分和のリストを作成する。

手順

課題4：数列の和の列2

目的

series-iter関数を使用して階乗の逆数の和の部分和のリストを作成する。

手順

課題5：sin関数のテーラー展開

目的

例題7のcos関数と同様の方法で、sin関数のテーラー展開を実装する。

手順

課題6：tan⁻¹関数のテーラー展開

目的

tan⁻¹関数（逆正接関数、arctangent）のテーラー展開を実装する。

手順

例題間の依存関係

本演習の例題は段階的に構成されている。以下に依存関係を示す。

演習環境の準備

DrSchemeを起動し、言語設定を「Intermediate Student」に変更する。設定手順は以下のとおりである。

例題1：ball構造体

目的

手順

ヒント

例題2：ballの原点からの距離

目的

手順

ヒント

例題3：ステップ実行

目的

手順

ヒント

例題4：AddressNote構造体

目的

手順

ヒント

例題5：住所録

目的

手順

ヒント

例題6：複素数の計算

目的

手順

ヒント

例題7：複素数のべき乗

目的

手順

ヒント

課題1：distance-to-0の実行

目的

手順

ヒント

課題2：関数inの作成

目的

手順

ヒント

課題3：年齢による分類

目的

手順

ヒント

課題4：関数check-by-ageの作成

目的

手順

ヒント

課題5：関数selection-by-ageの作成

目的

手順

ヒント

課題6：関数sum-ageの作成（年齢の平均）

目的

手順

ヒント

補足：ドモアブルの定理

目的

手順

ヒント

事前準備

DrSchemeの起動と設定

DrScheme（現在はRacketとして知られる処理系の旧名称）を使用するための初期設定を行う。

例題1：簡単な絵を描く

目的：

DrSchemeの描画機能であるdraw.ss teachpackを使用し、線、矩形、円などの基本図形を描画する方法を習得する。

例題2：ball構造体を描く

目的：

構造体（複数の属性をまとめたデータ型）とグラフィックス処理を組み合わせ、構造体のデータを用いて描画を行う方法を学ぶ。

例題3：リストの変数定義

目的：

define を使用してリストを値とする変数を定義し、リスト操作関数の動作を確認する。

例題4：構造体のリスト

目的：

構造体のリストを定義し、リスト操作と構造体のセレクタを組み合わせて使用する方法を学ぶ。

例題5：頂点のリストを値とする変数の定義

目的：

posn構造体（DrSchemeに組み込み済みの座標を表す構造体）のリストを定義し、図形の頂点データを表現する方法を学ぶ。

例題6：折れ線

目的：

再帰（関数が自分自身を呼び出す手法）を用いて、頂点のリストから折れ線を描画する関数を作成する。

例題7：多角形

目的：

例題6の折れ線描画を拡張し、終点と始点を結んで多角形を描画する関数を作成する。

課題1：描画命令の実行

目的：

描画関数のパラメータを変更し、異なるサイズ・位置での描画結果を確認する。

課題2：ボールの速さを求める関数

目的：

ball構造体から速度成分を取り出し、数学的な計算を行う関数を作成する。

課題3：境界判定関数

目的：

ball構造体の位置を評価し、条件分岐を用いて境界外かどうかを判定する関数を作成する。

課題4：2点間の距離を求める関数

目的：

点を表す構造体を自分で定義し、2点間の距離を計算する関数を作成する。

課題5：複数のballを描画

目的：

リストの再帰処理を用いて、複数のball構造体を描画する関数を作成する。

課題6：複数のballを消す

目的：

課題5と同様のパターンで、複数のballを消去する関数を作成する。

補足：例題8：ballを1秒描く

目的：

タイマー機能を用いて、一定時間だけ図形を表示してから消去する処理を学ぶ。

補足：例題9：動くballを描く

目的：

再帰とタイマーを組み合わせて、ballが移動するアニメーションを作成する。

課題7：複数のballを動かす

目的：

リストの各要素に対して移動処理を適用する関数を作成する。

課題8：境界外判定とウインドウ制御

目的：

条件判定を組み込み、すべてのballが境界外になったらアニメーションを終了する機能を実装する。

課題9：複数ballのアニメーション

目的：

例題9を拡張し、複数のballが同時に動くアニメーションを作成する。

課題10：動的な大きさ・色の変化

目的：

アニメーション中にballの属性（大きさや色）を変化させる機能を追加する。

課題11：跳ね返り処理

目的：

境界に達したballが跳ね返る物理シミュレーションを実装する。

例題1：階乗

目的

再帰的定義に基づいて階乗関数を作成し、再帰呼び出しの基本構造を理解する。

手順

1. DrSchemeを起動し、Intermediate Studentモードに設定する。
2. 定義用ウインドウに以下のコードを入力する。

   ;;! : number -> number
   ;;to compute n*(n-1)*...*2*1
   (define (! n)
     (cond
       [(= n 0) 1]
       [else (* n (! (- n 1)))]))

3. Executeボタンを押してプログラムを読み込む。
4. 実行用ウインドウで (! 3) と (! 4) を実行し、結果を確認する。
5. 関数定義の構造を確認する。終了条件（n = 0のとき1を返す）と再帰呼び出し（n × (n-1)!を計算）の2つの部分に注目する。

例題2：ステップ実行（階乗）

目的

DrSchemeのstepper機能を用いて、再帰呼び出しがどのように展開・収縮するかを視覚的に理解する。

手順

1. 例題1のコードに (! 3) を追加し、定義用ウインドウに入力する。

   ;;! : number -> number
   ;;to compute n*(n-1)*...*2*1
   (define (! n)
     (cond
       [(= n 0) 1]
       [else (* n (! (- n 1)))]))
   (! 3)

2. Executeボタンを押す。
3. Stepボタンを押してステップ実行を開始する。
4. Nextボタンを押しながら、各ステップでの式の変化を観察する。
5. 以下の展開過程を確認する。
   • (! 3) → (* 3 (! 2)) → (* 3 (* 2 (! 1))) → (* 3 (* 2 (* 1 (! 0))))
   • (* 3 (* 2 (* 1 1))) → (* 3 (* 2 1)) → (* 3 2) → 6

例題3：反復的プロセスでの階乗

目的

反復的プロセス（iterative process）による階乗計算を実装し、線形再帰的プロセスとの違いを理解する。

手順

1. 定義用ウインドウに以下のコードを入力する。

   ;; ! : number -> number
   ;; to compute n*(n-1)*...*2*1
   ;; (! 4) = 24
   (define (! n)
     (factorial 1 1 n))
   (define (factorial product counter max)
     (cond
       [(> counter max) product]
       [else (factorial (* counter product)
                        (+ counter 1)
                        max)]))

2. Executeボタンを押す。
3. 実行用ウインドウで (! 4)、(! 10)、(! 20) を実行する。
4. factorial 関数の3つの引数（product、counter、max）の役割を確認する。

例題4：ステップ実行（反復的プロセス）

目的

反復的プロセスの実行過程をstepperで確認し、線形再帰的プロセスとの違いを明確にする。

手順

1. 例題3のコードに (! 4) を追加し、定義用ウインドウに入力する。
2. Executeボタンを押す。
3. Stepボタン、Nextボタンを使ってステップ実行を行う。
4. 以下の過程を確認する。
   • (factorial 1 1 4) → (factorial 1 2 4) → (factorial 2 3 4) → (factorial 6 4 4) → (factorial 24 5 4) → 24
5. 各ステップでproductとcounterの値がどう変化するかを記録する。

例題5：繰り返し回数

目的

リスト処理における関数の繰り返し回数について考察する。

手順

1. 以下のコードを定義用ウインドウに入力する。

   (define (square x) (* x x))
   (define (total-square x)
     (cond
       [(empty? x) 0]
       [else (+ (square (first x))
                (total-square (rest x)))]))

2. Executeボタンを押す。
3. (total-square (list 10 20 30)) を実行し、結果が1400になることを確認する。
4. square 関数が何回実行されるかを考える。

例題6：最大公約数の計算

目的

ユークリッドの互除法（Euclidean algorithm）を用いて最大公約数を求める関数を作成する。

手順

1. 定義用ウインドウに以下のコードを入力する。

   ;; my-gcd: number number -> number
   ;; to find the greatest common divisor of n and m
   ;; Example: (my-gcd 180 32) = 4
   (define (my-gcd m n)
     (cond
       [(= n 0) m]
       [else (my-gcd n (remainder m n))]))

2. Executeボタンを押す。
3. 実行用ウインドウで (my-gcd 180 32) を実行し、結果が4になることを確認する。

例題7：ステップ実行（最大公約数）

目的

ユークリッドの互除法の実行過程をstepperで確認し、繰り返し回数を数える。

手順

1. 例題6のコードに (my-gcd 180 32) を追加し、定義用ウインドウに入力する。
2. Executeボタンを押す。
3. Stepボタン、Nextボタンを使ってステップ実行を行う。
4. 以下の過程を確認する。
   • (my-gcd 180 32) → (my-gcd 32 20) → (my-gcd 20 12) → (my-gcd 12 8) → (my-gcd 8 4) → (my-gcd 4 0) → 4
5. my-gcd が何回呼び出されるかを数える。

課題1：my-gcdの実行過程

目的

例題6〜7で学んだユークリッドの互除法の理解を確認し、異なる入力での実行過程を説明できるようになる。

手順

1. 例題7と同様の手順で、(my-gcd 210 66) をステップ実行する。
2. 各ステップでmとnの値がどう変化するかを記録する。
3. 最終的に6が得られる過程を数行程度で説明文にまとめる。

課題2：sum-coins関数

目的

リストを引数とする再帰関数の構造を理解し、空欄補充によってプログラムを完成させる。

手順

1. 以下のコードの空欄を埋める。

   ;; Contract: sum-coins : a-list-of-numbers a-list-of-numbers -> number
   ;; Example: (sum-coins (list 23 0 5 7) (list 1 5 10 25)) = 248
   (define (sum-coins a b)
     (cond
       [(   ) ]
       [else (+ (*  (   ) (   ))
                (   (   ) (   )))]))

2. 完成したコードをDrSchemeで実行する。
3. (sum-coins (list 23 0 5 7) (list 1 5 10 25)) の結果が248になることを確認する。
4. 別の入力値でも動作を確認する。

課題3：繰り返し回数の比較

目的

同じ問題を解く2つの異なるアルゴリズムの効率を比較し、アルゴリズムの選択が重要であることを理解する。

手順

1. 例題6のユークリッドの互除法による my-gcd を用意する。
2. 別方式の gcd-structural を入力する。

   (define (first-divisor n m i)
     (cond
       [(= i 1) 1]
       [else (cond
               [(and (= (remainder n i) 0)
                     (= (remainder m i) 0)) i]
               [else (first-divisor n m (- i 1))])]))
   (define (gcd-structural n m)
     (first-divisor n m (min n m)))

3. 同じ入力（例：180と32、210と66など）で両方の関数を実行する。
4. stepperを使って、それぞれの関数が何回繰り返されるかを数える。
5. 繰り返し回数の違いについて、自分なりの考察をまとめる。

課題4：エラトステネスのふるい

目的

エラトステネスのふるい（Sieve of Eratosthenes）の原理を理解し、100以下の素数を求めるプログラムを作成する。

手順

1. エラトステネスのふるいの原理を理解する。
   • 2から始めて、2の倍数（4, 6, 8, ...）を消す
   • 次に残っている数（3）の倍数を消す
   • 次に残っている数（5）の倍数を消す
   • これを√100 = 10を超えるまで繰り返す
2. 以下の機能を持つ関数を設計する。
   • 2からnまでの整数のリストを生成する関数
   • リストからある数の倍数を取り除く関数
   • ふるいの処理を繰り返す関数
3. 各関数を実装し、テストする。
4. 最終的に100以下の素数のリストが得られることを確認する。

;; range: number number -> list-of-numbers
;; 整数startからendまでのリストを生成する
;; Example: (range 2 10) = (list 2 3 4 5 6 7 8 9 10)
(define (range start end)
  (cond
    [(> start end) empty]
    [else (cons start (range (+ start 1) end))]))

;; remove-multiples: number list-of-numbers -> list-of-numbers
;; リストからnの倍数（n自身を除く）を取り除く
;; Example: (remove-multiples 2 (list 2 3 4 5 6)) = (list 2 3 5)
(define (remove-multiples n lst)
  (cond
    [(empty? lst) empty]
    [(and (> (first lst) n)
          (= (remainder (first lst) n) 0))
     (remove-multiples n (rest lst))]
    [else (cons (first lst)
                (remove-multiples n (rest lst)))]))

;; sieve: list-of-numbers -> list-of-numbers
;; エラトステネスのふるいを適用して素数のリストを返す
;; Example: (sieve (list 2 3 4 5 6 7 8 9 10)) = (list 2 3 5 7)
(define (sieve lst)
  (cond
    [(empty? lst) empty]
    [else (cons (first lst)
                (sieve (remove-multiples (first lst)
                                         (rest lst))))]))

;; primes-up-to: number -> list-of-numbers
;; n以下の素数のリストを返す
;; Example: (primes-up-to 100) = (list 2 3 5 7 11 ... 97)
(define (primes-up-to n)
  (sieve (range 2 n)))

(primes-up-to 100)

(list 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)

課題１：接線の傾きの計算

;; d/dx: (number->number) number number -> number
;; inclination of the tangent
;; Example: (d/dx f 3 0.0001)
;;        = ((- (f 3.0001) (f 2.9999)) 0.0002)
(define (d/dx f x h)
  (/ (- (f (+ x h)) (f (- x h))) (* 2 h)))

;; f2: number -> number
;; f(x) = x * cos(x)
(define (f2 x)
  (* x (cos x)))

手順

1. 上記のコードを「定義用ウインドウ」に入力し、Execute ボタンを押す。
2. 「実行用ウインドウ」で以下の4つの式を順に実行する。

   (d/dx f2 0 0.1)
   (d/dx f2 0.2 0.1)
   (d/dx f2 0.4 0.1)
   (d/dx f2 0.6 0.1)

3. 各実行結果を記録する。

演習２：刻み幅と誤差の関係（数値微分）

;; d/dx: (number->number) number number -> number
;; inclination of the tangent
(define (d/dx f x h)
  (/ (- (f (+ x h)) (f (- x h))) (* 2 h)))

;; f2: number -> number
;; f(x) = x * cos(x)
(define (f2 x)
  (* x (cos x)))

手順

1. 上記のコードを「定義用ウインドウ」に入力し、Execute ボタンを押す。
2. 特定の x の値（例：x = 0.4）に対して、以下の3つの h の値で d/dx を実行する。

   (d/dx f2 0.4 0.1)
   (d/dx f2 0.4 0.01)
   (d/dx f2 0.4 0.001)

3. 各結果を記録し、理論値 f'(0.4) = cos(0.4) - 0.4 × sin(0.4) と比較して誤差を計算する。
4. h の値を横軸、誤差の絶対値を縦軸としたグラフを作成する。

演習３：台形則による数値積分

;; trapezoid-iter: (number->number) number number number -> number
;; helper function for trapezoid
(define (trapezoid-iter f a h k)
  (cond
    [(= k 1) (f (+ a h))]
    [else (+ (f (+ a (* h k)))
             (trapezoid-iter f a h (- k 1)))]))

;; trapezoid: (number->number) number number number -> number
;; to compute the area under the graph of f between a and b
(define (trapezoid f a b n)
  (* (/ (- b a) n)
     (+ (trapezoid-iter f a (/ (- b a) n) (- n 1))
        (/ (f a) 2)
        (/ (f b) 2))))

;; f2: number -> number
;; f(x) = 1 / (1 + x)
(define (f2 x)
  (/ 1 (+ 1 x)))

手順

1. 上記のコードを「定義用ウインドウ」に入力し、Execute ボタンを押す。
2. 「実行用ウインドウ」で以下を実行する。

   (trapezoid f2 0 1 1000)

3. 比較のため、以下を実行して log 2 の値を確認する。

   (log 2)

4. 両者の差を計算し、近似の精度を確認する。

演習４：分割数と誤差の関係（数値積分）

;; trapezoid-iter: (number->number) number number number -> number
;; helper function for trapezoid
(define (trapezoid-iter f a h k)
  (cond
    [(= k 1) (f (+ a h))]
    [else (+ (f (+ a (* h k)))
             (trapezoid-iter f a h (- k 1)))]))

;; trapezoid: (number->number) number number number -> number
;; to compute the area under the graph of f between a and b
(define (trapezoid f a b n)
  (* (/ (- b a) n)
     (+ (trapezoid-iter f a (/ (- b a) n) (- n 1))
        (/ (f a) 2)
        (/ (f b) 2))))

;; f2: number -> number
;; f(x) = 1 / (1 + x)
(define (f2 x)
  (/ 1 (+ 1 x)))

手順

1. 上記のコードを「定義用ウインドウ」に入力し、Execute ボタンを押す。
2. 以下の6通りの分割数で trapezoid を実行する。

   (trapezoid f2 0 1 4)
   (trapezoid f2 0 1 8)
   (trapezoid f2 0 1 16)
   (trapezoid f2 0 1 32)
   (trapezoid f2 0 1 64)
   (trapezoid f2 0 1 128)

3. 各結果と (log 2) の値との差（誤差）を計算する。
4. 分割数 n を横軸、誤差の絶対値を縦軸としたグラフを作成する。
5. 誤差が c/n²（c は定数）の関係に従っているか確認する。n を2倍にしたとき誤差が約1/4になっていれば、この関係が成り立っている。

演習４（グラフィックス）：関数と接線のグラフ表示

;; d/dx: (number->number) number number -> number
;; inclination of the tangent
;; Example: (d/dx f 3 0.0001)
;;        = ((- (f 3.0001) (f 2.9999)) 0.0002)
(define (d/dx f x h)
  (/ (- (f (+ x h)) (f (- x h))) (* 2 h)))

;; samples: (number->number) number number number -> list of 'posn' structure
(define (samples f a h k)
  (cond
    [(= k 1) (cons (make-posn (+ a h) (f (+ a h))) empty)]
    [else (cons (make-posn (+ a (* h k)) (f (+ a (* h k))))
                (samples f a h (- k 1)))]))

; window size
(define WX 500)
(define WY 500)

; grid color, axis color and graph color
(define GRID_COLOR 'blue)
(define AXIS_COLOR 'red)
(define GRAPH_COLOR 'red)

; draw-a-line
(define (sessen x px py d)
  (+ (* d (- x px)) py))

(define (draw-a-sessen from to px py d x0 y0 sx sy)
  (draw-solid-line
   (make-posn (+ (* from sx) x0)
              (+ (* (sessen from px py d) sy) y0))
   (make-posn (+ (* to sx) x0)
              (+ (* (sessen to px py d) sy) y0))
   GRAPH_COLOR))

(define (draw-sessen f px x0 y0 sx sy)
  (draw-a-sessen (/ (- x0) sx) (/ (- WX x0) sx) px (f px)
                 (d/dx f px 0.00001) x0 y0 sx sy))

; draw-polyline
(define (draw-polyline a-poly)
  (cond
    [(empty? (rest a-poly)) true]
    [else (and (draw-solid-line (first a-poly)
                                (first (rest a-poly))
                                GRAPH_COLOR)
               (draw-polyline (rest a-poly)))]))

; draw-h-lines
(define (draw-h-lines start skip stop width)
  (cond
    [(>= start stop)
     (draw-solid-line (make-posn 0 stop)
                      (make-posn width stop)
                      GRID_COLOR)]
    [else (and (draw-solid-line (make-posn 0 start)
                                (make-posn width start)
                                GRID_COLOR)
               (draw-h-lines (+ start skip) skip stop width))]))

; draw-v-lines
(define (draw-v-lines start skip stop height)
  (cond
    [(>= start stop)
     (draw-solid-line (make-posn stop 0)
                      (make-posn stop height)
                      GRID_COLOR)]
    [else (and (draw-solid-line (make-posn start 0)
                                (make-posn start height)
                                GRID_COLOR)
               (draw-v-lines (+ start skip) skip stop height))]))

; (x0, y0) is the origin. sx and sy represent one grid size
(define (draw-grid x0 y0 sx sy)
  (and (draw-v-lines (- x0 (* (quotient x0 sx) sx)) sx
                     (+ (* (quotient (- WX x0) sx) sx) x0) WY)
       (draw-h-lines (- y0 (* (quotient y0 sy) sy)) sy
                     (+ (* (quotient (- WY y0) sy) sy) y0) WX)
       (draw-solid-line (make-posn 0 y0) (make-posn WX y0) AXIS_COLOR)
       (draw-solid-line (make-posn x0 0) (make-posn x0 WY) AXIS_COLOR)))

; (x0, y0) is the origin. sx and sy represent one grid size
(define (scaling a-list x0 y0 sx sy)
  (cond
    [(empty? a-list) empty]
    [else (cons (make-posn (+ (* (posn-x (first a-list)) sx) x0)
                           (+ (* (posn-y (first a-list)) sy) y0))
                (scaling (rest a-list) x0 y0 sx sy))]))

;; f2: number -> number
;; この関数を別のものに変更して実行すること
(define (f2 x)
  (- (* x x) 2))

; (X0, Y0) represents the origin of the graph.
; SX and SY represent the size of one grid
(define X0 (/ WX 2))
(define Y0 (/ WY 2))
(define SX 50)
(define SY 50)
(define PX 0.5)

(start WX WY)
(draw-grid X0 Y0 SX SY)
(draw-polyline (scaling (samples f2 (/ (- X0) SX) (/ 1 SX) WX) X0 Y0 SX SY))
(draw-sessen f2 PX X0 Y0 SX SY)

手順

1. 上記のコード全体を「定義用ウインドウ」に入力する。
2. Execute ボタンを押してプログラムを実行する。グラフウインドウが開き、f2(x) = x² - 2 のグラフと x = 0.5 における接線が表示される。
3. f2 の定義を別の関数に変更する。例えば以下のいずれかに変更する。

   (define (f2 x) (sin x))

   または

   (define (f2 x) (* x (cos x)))

4. 再度 Execute ボタンを押し、変更後のグラフと接線を確認する。
5. 必要に応じて PX の値（接線を描く x 座標）を変更し、異なる点での接線を観察する。

例題1：ニュートン法による非線形方程式の解

目的

手順

1. DrSchemeを起動し、言語設定を「Intermediate Student」に変更する（Language → Choose Language → Intermediate Student → Executeボタン）
2. 定義用ウインドウに以下のコードを入力し、Executeボタンを押す

;; d/dx: (number->number) number number -> number
;; inclination of the tangent
(define (d/dx f x h)
  (/ (- (f (+ x h)) (f (- x h))) (* 2 h)))

(define (is-good? f guess delta)
  (< (abs (f guess)) delta))

(define (improve f guess)
  (- guess (/ (f guess) (d/dx f guess 0.0001))))

;; newton: (number->number) number number number -> number
(define (newton f guess delta number)
  (cond
    [(or (is-good? f guess delta) (< number 0)) guess]
    [else (newton f (improve f guess) delta (- number 1))]))

(define (f2 x)
  (+ (* x x x) (* -6 x x) (* 11 x) -6))

3. 実行用ウインドウで以下を実行する

(newton f2 #i0 0.00001 10000)

4. 結果として約1に近い値（#i0.9999987646860998）が得られることを確認する
5. 初期値を変えて以下を実行し、異なる解（約3）が得られることを確認する

(newton f2 #i10 0.00001 10000)

ヒント

課題1：立方根を求めるプログラム

目的

手順

1. 立方根を求める問題を方程式として定式化する：x³ − a = 0 の解xが ∛a である
2. Schemeで関数fを定義する。aを具体的な数値（例：8）に置き換えて記述する

;; 例：8の立方根を求める場合
(define (f-cube x)
  (- (* x x x) 8))

3. newton関数を用いて解を求める

(newton f-cube #i1 0.00001 10000)

4. 負の数（例：a = −8）に対しても実行し、負の立方根（−2）が正しく求まることを確認する

;; -8の立方根を求める場合
(define (f-cube-neg x)
  (- (* x x x) -8))

(newton f-cube-neg #i-1 0.00001 10000)

5. deltaの値を0.1, 0.01, 0.001, 0.00001などに変えて実行し、得られる解の精度の変化を記録する

ヒント

課題2：ニュートン法での収束

目的

手順

1. f(x) = x² − 5 のグラフを手書きで描く（放物線、x軸との交点は ±√5 ≈ ±2.236）
2. Schemeで関数fを定義する

(define (f x)
  (- (* x x) 5))

3. 初期値 x₀ = 1 としてニュートン法を実行し、x₁, x₂, x₃ の値を記録する

(newton f #i1 0.00001 10000)

4. プログラムの途中経過から x₁, x₂, x₃ の値を読み取る
5. グラフ上に点 (x₀, f(x₀)) をプロットし、その点での接線を描く
6. 接線とx軸の交点が x₁ であることを確認し、同様に x₂, x₃ まで図示する

ヒント

課題3：(x − 1)⁴(x − 2) = 0 を解く

目的

手順

1. 関数 f(x) = (x − 1)⁴(x − 2) をSchemeで定義する

;; (x-1)^4(x-2) を展開すると x^5 - 6x^4 + 14x^3 - 16x^2 + 9x - 2
(define (f3 x)
  (+ (* x x x x x) (* -6 x x x x) (* 14 x x x) (* -16 x x) (* 9 x) -2))

2. 様々な初期近似値（例：0, 0.5, 1.5, 3, 10）でnewtonを実行する

(newton f3 #i0 0.00001 10000)
(newton f3 #i0.5 0.00001 10000)
(newton f3 #i1.5 0.00001 10000)
(newton f3 #i3 0.00001 10000)
(newton f3 #i10 0.00001 10000)

3. 各初期値に対して得られた解を記録し、どの解（1または2）に収束したかを整理する
4. 解1は4重解、解2は単解であることに注意し、収束の速さの違いを観察する

ヒント

演習4：f(x) = tan⁻¹x + 0.3x を解く

目的

手順

1. 関数 f(x) = tan⁻¹x + 0.3x をSchemeで定義する（tan⁻¹ は atan を使用）

(define (f4 x)
  (+ (atan x) (* 0.3 x)))

2. 様々な初期近似値で実行し、収束する場合と収束しない場合を記録する

(newton f4 #i0.1 0.00001 10000)
(newton f4 #i1 0.00001 10000)
(newton f4 #i5 0.00001 10000)
(newton f4 #i10 0.00001 10000)

3. f(x) のグラフを描き、解の位置を確認する
4. 収束しない初期値について、接線とx軸の交点を順次図示し、発散の様子を視覚化する
5. f'(x) = 1/(1 + x²) + 0.3 を計算し、導関数の符号変化と収束失敗の関係を考察する

ヒント

例題2：区間二分法による非線形方程式の解

目的

手順

1. 区間二分法の原理を確認する：f(a) < 0 かつ f(b) > 0 ならば、[a, b] の間に解が存在する
2. 定義用ウインドウに以下のコードを入力し、Executeボタンを押す

(define (f x)
  (- (* x x) 2))

(define (good-enough? a b)
  (< (- b a) 0.000001))

(define (middle a b)
  (/ (+ a b) 2))

(define (half-interval a b)
  (cond
    [(good-enough? a b) a]
    [else
     (cond
       [(< (f (middle a b)) 0) (half-interval (middle a b) b)]
       [(= (f (middle a b)) 0) (middle a b)]
       [(> (f (middle a b)) 0) (half-interval a (middle a b))])]))

3. 実行用ウインドウで以下の3つを実行し、結果を比較する

(half-interval 0 2)    ;; 正しい解（約1.414）が得られる
(half-interval -2 0)   ;; 正しくない結果になる
(half-interval 2 4)    ;; 正しくない結果になる

4. 正しい解が得られない場合の原因を考察する

ヒント

例題3：区間二分法での繰り返し処理

目的

手順

1. 定義用ウインドウに以下のコードを入力する（例題2のコードに (half-interval 0 2) を追加）

(define (f x)
  (- (* x x) 2))

(define (good-enough? a b)
  (< (- b a) 0.000001))

(define (middle a b)
  (/ (+ a b) 2))

(define (half-interval a b)
  (cond
    [(good-enough? a b) a]
    [else
     (cond
       [(< (f (middle a b)) 0) (half-interval (middle a b) b)]
       [(= (f (middle a b)) 0) (middle a b)]
       [(> (f (middle a b)) 0) (half-interval a (middle a b))])]))

(half-interval 0 2)

2. ExecuteボタンではなくStepボタンを押す
3. Nextボタンを繰り返し押し、各ステップでの変数の値を確認する
4. 以下の過程を追跡する
   • (half-interval 0 2) → (half-interval 1 2) → (half-interval 1 3/2) → ...
5. a と b の値が徐々に近づき、区間が縮小していく様子を観察する

ヒント

環境設定

本演習ではDrSchemeを使用する。起動後、言語設定を「Intermediate Student」に変更すること。

ステッパ機能について

DrSchemeのステッパ（Stepper）機能は、プログラムの実行過程を1ステップずつ確認できるデバッグツールである。再帰関数の動作を理解する際に有用である。

例題1：要素の挿入

目的

ソート済みリスト（降順に並んだリスト）に新しい要素を適切な位置に挿入する再帰関数の構造を理解する。

手順

;; insert: number list-of-numbers(sorted) -> list-of-numbers(sorted)
;; ソート済みリスト alon に数値 n を挿入し、ソート済みリストを返す
(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)))])]))

(insert 40 (list 80 21 10 7 5 4))

(insert 100 (list 80 21 10))
(insert 1 (list 80 21 10))

例題2：インサーションソート

目的

例題1のinsert関数を活用し、リスト全体を降順にソートするインサーションソート（挿入ソート）のアルゴリズムを実装する。

手順

;; sort: list-of-numbers -> list-of-numbers
;; リスト alon を降順にソートする
(define (sort alon)
  (cond
    [(empty? alon) empty]
    [else (insert (first alon)
                  (sort (rest alon)))]))

;; insert: number list-of-numbers(sorted) -> list-of-numbers(sorted)
(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)))])]))

(sort (list 3 5 1 4))

(sort (list 10 2 8 4 6))
(sort (list 1))
(sort empty)

例題3：インサーションソートでの繰り返し回数

目的

再帰関数の実行回数とデータサイズの関係を分析し、アルゴリズムの計算量（時間計算量）について理解する。

手順

(sort (list 80 30 50))

例題4：append

目的

Schemeの組み込み関数appendの動作を確認し、複数のリストを連結する方法を理解する。

手順

(append (list 1 2) (list 3 4))
(append (list 1 2) (list 3 4) (list 5 6))
(append (list 1 2) 3 (list 4 5))

例題5：大きな要素の選択

目的

リストから条件を満たす要素のみを抽出するフィルタリング処理を実装する。ここではthreshold以上の要素を選択する。

手順

;; larger-items: list-of-numbers number -> list-of-numbers
;; alon から threshold 以上の数を選びリストを作る
(define (larger-items alon threshold)
  (cond
    [(empty? alon) empty]
    [else (cond
            [(>= (first alon) threshold)
             (cons (first alon)
                   (larger-items (rest alon) threshold))]
            [else (larger-items (rest alon) threshold)])]))

(larger-items (list 1 2 3 10 11 12 4 5 6) 6)

(larger-items (list 1 2 3 10 11 12 4 5 6) 10)
(larger-items (list 1 2 3 10 11 12 4 5 6) 1)

例題6：小さな要素の選択

目的

例題5と対になる処理として、thresholdより小さい要素を選択する関数を実装する。

手順

;; smaller-items: list-of-numbers number -> list-of-numbers
;; alon から threshold より小さな数を選びリストを作る
(define (smaller-items alon threshold)
  (cond
    [(empty? alon) empty]
    [else (cond
            [(< (first alon) threshold)
             (cons (first alon)
                   (smaller-items (rest alon) threshold))]
            [else (smaller-items (rest alon) threshold)])]))

(smaller-items (list 1 2 3 10 11 12 4 5 6) 6)

例題7：クイックソート

目的

分割統治法（divide and conquer）に基づくクイックソートアルゴリズムを実装する。例題4-6で作成した関数を組み合わせて使用する。

手順

;; larger-items: list-of-numbers number -> list-of-numbers
(define (larger-items alon threshold)
  (cond
    [(empty? alon) empty]
    [else (cond
            [(>= (first alon) threshold)
             (cons (first alon)
                   (larger-items (rest alon) threshold))]
            [else (larger-items (rest alon) threshold)])]))

;; smaller-items: list-of-numbers number -> list-of-numbers
(define (smaller-items alon threshold)
  (cond
    [(empty? alon) empty]
    [else (cond
            [(< (first alon) threshold)
             (cons (first alon)
                   (smaller-items (rest alon) threshold))]
            [else (smaller-items (rest alon) threshold)])]))

;; quick-sort: list-of-numbers -> list-of-numbers
;; リストを昇順にソートする
(define (quick-sort alon)
  (cond
    [(empty? alon) empty]
    [else (append
            (quick-sort (smaller-items (rest alon) (first alon)))
            (list (first alon))
            (quick-sort (larger-items (rest alon) (first alon))))]))

(quick-sort (list 4 6 2))
(quick-sort (list 8 10 6 3 5))

例題8：クイックソート（構造体）

目的

数値リストではなく、構造体のリストに対してクイックソートを適用する方法を学ぶ。文字列比較関数を用いて名前順にソートする。

手順

;; 構造体の定義
(define-struct address-record (name age address))

;; テストデータ
(define book
  (list (make-address-record "Mike" 10 "Fukuoka")
        (make-address-record "Bill" 20 "Saga")
        (make-address-record "Ken" 30 "Nagasaki")))

;; larger-items: list-of-address-record string -> list-of-address-record
;; a-list から threshold 以上の名前を持つレコードを選びリストを作る
(define (larger-items a-list threshold)
  (cond
    [(empty? a-list) empty]
    [else (cond
            [(string>=? (address-record-name (first a-list)) threshold)
             (cons (first a-list)
                   (larger-items (rest a-list) threshold))]
            [else (larger-items (rest a-list) threshold)])]))

;; smaller-items: list-of-address-record string -> list-of-address-record
;; a-list から threshold より小さな名前を持つレコードを選びリストを作る
(define (smaller-items a-list threshold)
  (cond
    [(empty? a-list) empty]
    [else (cond
            [(string<? (address-record-name (first a-list)) threshold)
             (cons (first a-list)
                   (smaller-items (rest a-list) threshold))]
            [else (smaller-items (rest a-list) threshold)])]))

;; quick-sort: list-of-address-record -> list-of-address-record
;; 名前のアルファベット順にソートする
(define (quick-sort a-list)
  (cond
    [(empty? a-list) empty]
    [else (append
            (quick-sort (smaller-items (rest a-list)
                                       (address-record-name (first a-list))))
            (list (first a-list))
            (quick-sort (larger-items (rest a-list)
                                      (address-record-name (first a-list)))))]))

(quick-sort book)

課題1：クイックソートの実行過程

目的

クイックソートの再帰的な実行過程を追跡し、分割統治法の動作原理を説明できるようになる。

手順

課題2：住所録構造体のクイックソート

目的

例題8のプログラムを実行し、構造体リストのソート結果を確認する。

手順

課題3：リスト検索プログラム

目的

リストから特定の要素を検索する関数を作成する。さらに、ソート済みリストの性質を活用した効率的な検索を考える。

課題3-1：基本的な検索

課題3-2：ソート済みリストの検索

課題3 解答例

課題3-1：search関数

;; search: number list-of-numbers -> boolean
;; 数 n がリスト a-list に存在するかどうかを判定する
;; 存在するときに限り true を返す
(define (search n a-list)
  (cond
    [(empty? a-list) false]
    [(= (first a-list) n) true]
    [else (search n (rest a-list))]))

テスト例：

(search 5 (list 1 3 5 7 9))   ;; => true
(search 4 (list 1 3 5 7 9))   ;; => false
(search 1 (list 1 2 3))       ;; => true
(search 10 empty)             ;; => false

課題3-2：search-sorted関数（昇順リスト版）

;; search-sorted: number list-of-numbers(sorted ascending) -> boolean
;; 昇順にソートされたリスト a-list から数 n を検索する
;; 存在するときに限り true を返す
;; ソート済みという性質を利用して効率的に検索を行う
(define (search-sorted n a-list)
  (cond
    [(empty? a-list) false]
    [(= (first a-list) n) true]
    [(> (first a-list) n) false]  ;; 昇順なので、これ以降にnは存在しない
    [else (search-sorted n (rest a-list))]))

テスト例：

(search-sorted 5 (list 1 3 5 7 9))   ;; => true
(search-sorted 4 (list 1 3 5 7 9))   ;; => false（4より大きい5で打ち切り）
(search-sorted 10 (list 1 3 5 7 9))  ;; => false
(search-sorted 1 (list 1 3 5 7 9))   ;; => true

課題3-2：search-sorted関数（降順リスト版）

;; search-sorted-desc: number list-of-numbers(sorted descending) -> boolean
;; 降順にソートされたリスト a-list から数 n を検索する
;; 存在するときに限り true を返す
(define (search-sorted-desc n a-list)
  (cond
    [(empty? a-list) false]
    [(= (first a-list) n) true]
    [(< (first a-list) n) false]  ;; 降順なので、これ以降にnは存在しない
    [else (search-sorted-desc n (rest a-list))]))

テスト例：

(search-sorted-desc 5 (list 9 7 5 3 1))   ;; => true
(search-sorted-desc 6 (list 9 7 5 3 1))   ;; => false（6より小さい5で打ち切り）
(search-sorted-desc 0 (list 9 7 5 3 1))   ;; => false
(search-sorted-desc 9 (list 9 7 5 3 1))   ;; => true

演習環境の準備

例題1：ペア

(define x (cons 'apple 100))
(define y (cons 'orange 60))
(define z (cons 'banana 80))

x
(car x)
(cdr x)

例題2：リストの変数定義

(define A (cons 15 (cons 8 (cons 6 '()))))

A
(car A)
(cdr A)

例題3：ペアから構成されたペア

(define a (cons (cons 1 2) (cons 3 4)))

a
(car a)
(cdr a)

例題4：carとcdrの組み合わせ

(define a (cons (cons 1 2) (cons 3 4)))

(car (car a))
(cdr (car a))
(car (cdr a))
(cdr (cdr a))

(caar a)
(cdar a)
(cadr a)
(cddr a)

例題5：consとlistの組み合わせ(1)

(define x (cons (list 1 2 3) (list 4 5 6)))

x
(car x)
(cdr x)

例題6：consとlistの組み合わせ(2)

(define x (list (cons 'x 'y) (cons 'a 'b) (cons 10 20)))

x
(car x)
(cadr x)
(caddr x)

例題7：listとlistの組み合わせ

(define x (list (list 1 2) (list 3 4)))

x
(car x)
(cadr x)
(car (car x))
(cadr (cadr x))

例題8：二分探索木

(define-struct node (value left right))

(define tree
  (make-node 35
    (make-node 21
      (make-node 13 false false)
      false)
    (make-node 46
      (make-node 40 false false)
      (make-node 61
        false
        (make-node 69 false false)))))

(node-value tree)
(node-left tree)
(node-right tree)
(node-value (node-left tree))

例題9：二分探索木による探索

(define (search x a-tree)
  (cond
    [(eq? a-tree false) false]
    [(< x (node-value a-tree)) (search x (node-left a-tree))]
    [(< (node-value a-tree) x) (search x (node-right a-tree))]
    [else true]))

(search 40 tree)
(search 35 tree)
(search 100 tree)
(search 13 tree)

課題1

(list (cons 1 2) (cons 3 4))
(list (list 1 2) (list 3 4))

(car (list ...))
(cdr (list ...))
(cadr (list ...))
(cddr (list ...))

報告用テンプレート

例題1：フィボナッチ数（木構造再帰プロセス）

目的

手順

(define (fibo n)
  (cond
    [(= n 0) 0]
    [(= n 1) 1]
    [else (+ (fibo (- n 1)) (fibo (- n 2)))]))

(fibo 5)
(fibo 6)
(fibo 7)

ヒント

例題2：反復的プロセスでのフィボナッチ数

目的

手順

(define (fibo n)
  (fibo-iterate 1 0 n))

(define (fibo-iterate a b counter)
  (cond
    [(= counter 0) b]
    [else (fibo-iterate (+ a b) a (- counter 1))]))

(fibo 5)
(fibo 6)
(fibo 7)

ヒント

課題1：性能比較

目的

手順

ヒント

補足説明