第3章

関数型言語 Haskell とは（ 空欄 3.0.1 ）Haskell はと呼ばれ、ラムダ計算を基本としながらも実際の使用に便利な機能を追加したプログラミング言語である。Haskell と（型なし ）ラムダ計算との主な違いは

1. 整数などの定数を導入している。
（ 空欄 3.0.2 ）2. 式はされている。つまり、コンパイル時に（実行する前に ）型エラーが検出される。

3. 代数的データ型というユーザー定義のデータ型を定義することができる。
4. 代数的データ型に対してパターンマッチングによって場合分けすることができる。
5. グラフ簡約という手法によって実行される。
6. 中置記法の演算子を使用することができる。
などの点である。また、他のプログラミング言語と比べた時の特徴は、以下のようになる。
（ 空欄 3.0.3 ）を持ち、プログラマが メモリの管理に煩わされること

1.
がない。

2. 関数を他の関数の引数としたり、関数を生成して他の関数の戻り値とした（ 空欄 3.0.4 ）り、関数を一般の値として使うことができる（）
。
3. 多相型を許すことにより、汎用性のある関数を定義することができる。
4. 型推論により、（ほとんどの場合）プログラム中に型を書く必要はない。また、型クラスなど 、型システムが発達している。
（ 空欄 3.0.5 ）5. 式にはない。入出力や参照の書換えなど の効果も値として表現される。このため、プログラムの同値性などの性質に関する考察が、より容易になる。

6. 遅延評価を採用し 、グラフ簡約によって実行される。
一般に関数型言語は記号処理に適している。もちろん 、純関数型言語を C やJava などと同じように実世界のプログラミングに利用することも可能である。しかし 、ここでは、主に他のプログラミング言語を実装するための超言語として紹介することにする。

III - 1

3.1

Haskell 処理系の入手とインスト ール

Haskell の環境としてここでは Haskell Platform を利用することにする。Haskell
Platform は Haskell 処理系の GHC (Glasgow Haskell Compiler1 ) に標準的なツー
ル・ライブラリ・ド キュメントを付け加えたものである。GHC は Haskell の処
理系の事実上の標準（デファクト スタンダ ード ）である。Haskell Platform は 、
http://hackage.haskell.org/platform/ からダウンロード することができる。
Windows の場合、インストールは入手したファイルをダブルクリックするだけである。
また Linux 用のインストーラーなども上記のホームページから入手することが
できる。

3.2

GHCi のコマンド

GHC は、多くのプログラムの集合体であり、gcc や javac のように実行可能形
式を出力するバッチコンパイラ（ ghc ）もその中に含まれている。ここでは、その中で対話型の処理系である GHCi (ghci) の使用法を説明する。
GHCi を起動すると、
Prelude>のようなプロンプトが表示される。このプロンプトからコマンド を入力することによって、ファイルからプログラムをロードし 、式を評価することができる。
GHCi のコマンドには次のようなものがある。
コマンド:load file:also file
:reload:type expr
:cd directory:! command
:?
:main
:quit

省略形

:l
:a
:r
:t
:c

:ma
:q

意味

file をロード する。
file を追加ロード する。
以前にロードしたファイルをリロード する。
expr の型を表示する。
デ ィレクトリを変更する。
command をコマンドプロンプトに渡して実行する。
例: :!cd, :!dir, :!start. など
ヘルプを表示する。
main 関数を実行する
GHCi を終了する。

また、単に式を入力すると、その式を評価してその結果を出力する。

Prelude> 1+2
3

1

Guarded Horn Clauses という論理プログラミング言語と同じ頭文字だが 、何の関係もない。

III - 2（このテキスト中の実行例では、3 のように斜体になっているところがシステムの出力で、それ以外がユーザの入力である。）（ 空欄 3.2.1 ）Haskell のプログラムソースファイルには通常という拡張子をつける。

3.3 Haskell のプログラムの基本
Haskell の仕様書は http://www.haskell.org/から入手することができる。以下では、Haskell の仕様の基本的なところを紹介する。
変数の宣言 Haskell では他のプログラミング言語同様、変数を宣言して良く使う式に名前をつけることができる。ただし 、C 言語のような命令型言語と異なり、変数は一度宣言するとその値を変えることはできない（ 代入はできない）。
変数の宣言は次の形で行なう。
変数名 = 式
複数の変数をまとめて宣言する時は次の形式になる。

{
変数名 1 = 式 1 ;変数名 2 = 式 2 ;... ;変数名 n = 式 n}
つまり、前後を “{” と “}”（ブレース）で囲み、“; ”（セミコロン ）で区切る。ただし 、ブレースとセミコロンは多くの場合省略でき、以下のプログラム例でも原則として省略する。省略の詳細な条件は付録で説明する。
変数名には C 言語と同じようにアルファベット、数字、“_”（アンダースコア）
が使えるほか、 “’”（アポストロフィ）も使うことができる。アルファベットの大文字と小文字は区別する。ただし 、通常の変数名は小文字（またはアンダース
コア）から始まる必要がある。大文字から始まる名前は、後で紹介する構成子名に用いる。
プログラム Haskell のプログラムはモジュールの集合で、1 つのモジュールは基
本的には複数の変数の宣言の前に

module モジュール名 whereというヘッダ部分をつけた形式である。つまり、以下のようなかたちである。

module モジュール名 where {変数名 1 = 式 1 ;変数名 2 = 式 2 ;... ;変数名 n = 式 n}
III - 3

ただし変数の宣言の他に、import 宣言や型の宣言、型クラス関係の宣言などを書くことができる。これらについては後述する。通常、1 つのファイルに 1 つのモ
ジュールを記述する。
「 module モジュール名 where 」の部分を省略すると Main という名前のモジュールの定義と解釈される。ブレースやセミコロンも多くの場合省略されるので、もっとも簡単な場合、Haskell のプログラムは単に次のような形式をしていることになる。
変数名 1 = 式 1
変数名 2 = 式 2...
変数名 n = 式 n関数定義関数を定義するときは、仮引数を “=” の左辺に並べて、

id x
= x
twice x = 2*x
foo x y = 2*x+yのように書くことができる。関数 id や関数 twice の場合は、x が 、関数 foo の場合は x と y が仮引数である。
四則演算の演算子は、C や Java と共通のものが多いが、割り算関係などは異なる。異なる点は必要になった時点で説明する。
関数の適用は “twice 2” や “foo 3 4” のように関数と実引数を並べて書くだけである。
（その値はそれぞれ、4 と 10 になる） 通常の数学の記法や C 言語などのように引数に括弧をつける必要はない。もちろん演算の順番を明示するために“foo (twice 2) (id 3)” のように括弧を使用することはできる。
（この値は 11になる。）

Q 3.3.1 次のような関数を定義せよ。
1. 3 倍して 1 を引く関数 bar
2. 3 乗する関数 cube
ラムダ式 Haskell では、無名関数を表すのにラムダ式というラムダ計算に由来する記法を用いる。
（ただし 、日本語環境ではしばしば円マーク“ （ 空欄 3.3.1 ）”（バックスラッシュ）“Y=” になってしまう）のあとに仮引数を空白で区切って並べて書き、そのあとに“ （ 空欄 3.3.2 ）” 、つづけて関数本体の式を書く。例えば 、“\ x y -> 2*x+y” は、
2 つの引数 x, y を受け取り、x の 2 倍と y の和を返す関数である。ラムダ式は無名関数（あるいは匿名関数）とも言う。
（ラムダ計算とは、 “λ” の代わりに “\” を、“.”（ピリオド ） の代わりに “->”を用いる点が異なる。）

III - 4

ラムダ計算Haskell

λx.x
λxy.y
当然ながら、仮引数の名前は（ 他の変数と衝突しない限り）自由に選ぶことができる。例えば 、“\ x y -> 2*x+y” と “\ dog cat -> 2*dog+cat” は同じ関数を表す。このような変数名の付け替えを α 変換と言う。
上記の関数定義は、次の定義とまったく等価である。

id= \ x -> x
twice = \ x -> 2*x
foo= \ x y -> 2*x+y

Q 3.3.2 Q.3.3.1 の関数 bar, cube を、“変数 = ラムダ式” の形式で定義せよ。
コメント

Haskell のコメントには 2 つのかたちがある。

•（ 空欄 3.3.3 ）•というかたち（ 一行コメント ）（ 空欄 3.3.4 ）というかたち（ 複数行コメント ）3.4 組み込みのデータ型と演算子
Haskell では真偽値（ Bool ）、整数（ Int, Integer—Int は固定（ 有限）精度の整数, Integer は無限精度の整数）、浮動小数点数（ Float, Double ）、文字（ Char ）などは組み込みのデータ型として用意されている。Bool 型のリテラルは True とFalse であり、Integer, Float, Double, Char 型などのリテラルの記法は C 言語とほぼ同様である。
（ 0.2 の 0 は省略できないなど ，細かい相違はある。）
これらのデータ型に対しては組み込みの関数や演算子がいくつか用意されている。Lisp の場合と異なり、算術演算子の “+”, “-”, “*” などは、1+2*3 のように通常の中置記法で用いる。
if〜then〜else 式も組み込みで用意されている。次の形で用いる。
if 式 1 then 式 2 else 式 3式 1 は Bool 型でなければならず、式 2 と式 3 は同じ型でなければならない。式 1が True の時は式 2 、False の時は式 3 として評価される。なお、後で詳しく説明するが、if〜then〜else 式は、Haskell では特殊な評価順を必要とする特殊形式ではない。同様の働きをする通常の関数を定義することも可能である。
次の例は階乗（ factorial ）の関数の Haskell での宣言である。

fact n = if n==0 then 1 else n*fact(n-1)

III - 5

関数適用は他のどんな中置記法の演算子よりも（ 空欄 3.4.1 ）。そ（ 空欄 3.4.2 ）のため、fact(n-1) は fact n-1 と書くことはできない。後者はの意味になってしまう。逆に n*(fact(n-1)) の外側の括弧は必要ない。
なお、この例のように変数は定義することが可能である。つまり、定義の右辺に自分自身を使用することができる。再帰的定義に特別な文法を使用する必要はない。

問 3.4.1 fact 100 を計算してみよ。

Q 3.4.2 フィボナッチ数列を計算する関数 fib を（ 効率を気にせず単純に ）定義
せよ。
（ 発展）ガード ガード といって、仮引数の並びの後に “|” を書き、そのあとに条件式を書くことが出来る。ガード 節（「 | 条件式 = 右辺」のかたち）は複数個並べることが出来る。その場合、上（ 左）のガードから条件式を評価し 、真になった箇所の “=” の右辺を評価する。ガード を使うと、上記の fact の定義は次のよ
うに書くことが出来る。

1
2

fact n| n==0| otherwise= 1= n*fact(n-1)

リスト リスト型も組み込みのデータ型として用意されている。リストとは簡単に言えばデータの並びである。リストは伝統的に Scheme などの Lisp 系の言語が得意とするデータ型であり、Haskell でも豊富なライブラリ関数が用意されている。
リストは、空リスト （ 空欄 3.4.3 ）とコンス (cons) と呼ばれる演算子 “ （ 空欄 3.4.4 ）”から構成される。この 2 つをリストの構成子 (constructor) と呼ぶ。

• 空リスト（ [] ）は文字通り空のリストである。
• コンス（ : ）は右オペランド として渡されるリストの先頭に左オペランド として渡される要素を付け加えたリストを返す演算子である。
（ 空欄 3.4.5 ）また、“:” はである。つまり、1:2:[] は 1:(2:[]) のことを表す。
リストのリテラルの記法として、要素を “,”（コンマ）で区切って並べ、 “[” と“]” で囲む記法も用意されている。例えば [1,2,3,4] は、1:2:3:4:[] のことである。

Q 3.4.3 [1,2,3] と [[1,2],[3,4]] を : と [] （と括弧と整数リテラル ）だけで定義せよ。

III - 6

リスト型はパラメーターを持つ型である。つまり、リストの要素の型をパラメー（ 空欄 3.4.6 ）ターとする。要素の型が Integer 型の場合、そのリストの型は（ 空欄 3.4.7 ）型、要素の型が Double 型の場合リストの型は型と書き表される。型の異なる要素が混在するリストは作成できない。つまり、[2, ’a’,[2]] のような式は型エラーとなる。

Q 3.4.4 [False, True] の型と ["Kagawa", "University"] の型を書け。
String 型と type 宣言 Haskell の文字列（ String ）型は実は文字のリスト型として表されている。つまり、
type String = [Char]のように定義されている。ここで、type 型名 = 型
は型の別名（ type alias ）を宣言する形式である。上の例の場合 String という型
名が、[Char] という型の別名となる。型名は大文字から始まる識別子でなければならない。
箱ポインター記法 リストを、箱と矢印を用いた図（箱ポインター記法、box-pointer記法）で表すことがある。例えば 、次のように構成されたリストの場合、

xs0 = []
xs1 = 1:xs0
xs2 = 2:xs1
xs3 = 3:xs2
次の図のようになる。

xs3

xs2

xs1

3

2

1

1 つの “:” を 2 個の正方形の箱がつながった箱（コンスセル ）への矢印で表す。
箱の中身は、1, 2, 3 などの数、他の箱への矢印などである。
（ 箱の中に他の箱がまるごと入ることはない。）空リストは斜線を引いて表す。
式

箱ポインター記法

☆ △

☆:△

[]
また、[[1,2],[3,4]] というリストのリストは

III - 7

1

2

3

4

という箱ポインター記法（の左上の太い矢印）で表される。

Q 3.4.5 次のリストを箱ポインター記法で書け。
1.

[2,3,5,7,11]

2.

[0]

3.

[[1],[2,3,4],[]]（ 参考） リストを C 言語の構造体として定義すると次のようになる。

1
2
3
4
5
6

struct _list {int car;struct _list* cdr;}
typedef struct _list* list;_list という構造体は、car と cdr という 2 つのメンバを持つ。このうち cdr は
現在定義されている型へのポインタ型である。list という型は、typedef 宣言に
よって、struct _list*という型の別名として定義される。
（ 箱ポインター記法
で矢印になっているところが 、C 言語ではポインターとして表される。）
また、空リストは C 言語では通常、定数 NULL で表される。
malloc 関数が使われていることからわかるように、C 言語でリストを扱う場合
は、いつ free をするかを気を付けなければいけない。Haskell や他の関数型言語
ではゴ ミ集めという仕組みのおかげで明示的に free しなくても、いらなくなったメモリ領域は自動的に回収されることになっている。
組 組 (tuple) も 組み 込み のデ ー タ 型とし て 用 意され て い る 。組は 要 素を“,”（ コン マ ）で 区切って 並べ 、 “(” と “)” で 囲んで 表す。組は リスト の 場
合と 異なり、要素の 型が 同一であ る必要はない 。(1, ’a’) とい う式の 型はと表記され る。また 、(2, ’b’, [3]) という式の型はと表記される2 。

Q 3.4.6 次の式の型は何か？
1.
(False, "Hello")

2.

(’X’, ("Aloha", False))2

実際の Haskell では、型クラス（ type class ）というものが関係するため、これらの式はもう少し複雑な型を持つ。ここでは型クラスの説明は避けて、実際よりも単純化した型（ 整数リテラルはInteger, 浮動小数点数リテラルは Double ）を紹介している。

III - 8() という要素がゼロ個の組もある。ユニット (unit) と呼ばれる。() の型も ()と表記し 、ユニット型と呼ばれる。C 言語の void 型のような使い方をする。
関数型 関数の型は “->” とい う記号を 使って 、Integer -> Char のよ うに表記され る 。これ は 、引数の 型が Integer で 戻り 値の 型が Char の 関数の型である。“->” はである。つまり、Bool -> Bool -> Bool という型
はと解釈され る。Haskell では多引数関数を“関数を返す関数” として表現する（このことを “カリー化” という）ので、このように約束しておくほうが便利である。
多相型 Integer や Char のように型定数の名前は必ず大文字から始まる。一方 、a や b のように小文字で始まる識別子が 型の中に 現れ る場合 、これらはである。これらの型変数は使用する時に 、より具体的な型に置き換えることができる。例えば 、[a] -> [b] -> [(a, b)] という型を持つ関数は 、[Char] -> [Integer] -> [(Char, Integer)] という型を持つ関数として使用しても良いし 、[String] -> [Integer -> Integer] -> [(String, Integer-> Integer)] として使用しても良い。
このように型変数を含む型をという。Haskell はとともに多相型を許す代表的なプログラミング言語である。
なお、変数の型をプログラム中に明示したい場合 “::” という記号を使って、変数名 :: 型と書く。例えば id や fact の型を明示しておきたい場合は、

1
2
3
4
5

id :: a -> a
id x = xfact :: Integer -> Integer
fact n = if n==0 then 1 else n*fact(n-1)のように書く。ただし通常は、変数の型はプログラマが明示しなくても、Haskell
処理系が推論してくれる。この仕組みをという。

3.5 パターンマッチング
Haskell では、関数の仮引数の部分にというものを書いて、引数の形に応じて場合分けを行なう事が可能である3 。パターンとは、大雑把に言って変数と定数、構成子（ :や [] など ）からのみ生成される式である。
123fact :: Integer -> Integer
fact 0 = 1
fact n = n * fact (n-1)
3一般に関数型言語はデータの種類は増えずに処理（関数）が増えるような場合が得意、オブジェ
クト指向言語は、データ（ クラス）の種類が増えて、処理（ メソッド ）が増えないような場合が得意である。

III - 9

4
5
6
7
8

-- Prelude の length とほぼ同じ
myLength :: [a] -> Integer
myLength []= 0
myLength (x:xs) = 1 + myLength xs
この例の場合、myLength の引数が空リスト（ [] ）ならば 1 行目が選択される。一方、1 つ以上の要素を持つリストならば 2 行目が選択され 、リストの先頭要素が変数 x に束縛され、残りのリストが変数 xs に束縛される。
（なお、myLength とほ
とんど 同じ関数 length :: [a] -> Int が標準ライブラリに用意されている。）
パターンマッチングで、右辺で使わない部分には “_”（アンダースコア）を使って変数に束縛せず、無視することができる。例えば myLength の場合、x は右辺で使用していないので、

myLength (_:xs) = 1 + myLength xsと書くことができる。
case〜of 式もパターンマッチングを行なう。case〜of 式は次の形で用いる。
（やはり、ブレースとセミコロンは通常省略する。）

case 式 0 of {パターン 1 -> 式 1 ;パターン 2 -> 式 2 ;...
パターン n -> 式 n}
式 0 を評価して、上から順にパターンと照合し 、パターン 1 にマッチするならば式 1 が 、パターン m にマッチするならば式 m がそれぞれ評価される。
if 式 1 then 式 2 else 式 3 という式も次の case〜of 式の略記法と解釈することが可能である。

case 式 1 of { True -> 式 2 ; False -> 式 3 }この他に、let 式（ 後述）や λ 式など 変数を束縛するところでもパターンを書くこともできる。例えば 、\ (x,y) -> x
let (xs,ys) = unzip zs in xs++ysなどである。この場合は、パターンは一種類のみで場合分けはできず、パターンにマッチしない引数が与えられればエラーとなる。
問 3.5.1 リスト中の数の和を求める関数 mySum を定義せよ。
（ 同等の関数 sum は標準ライブラリに用意されている。）
問 3.5.2 リスト中の数の積を求める関数 myProd を定義せよ。
（同等の関数 productは標準ライブラリに用意されている。）

III - 10

問 3.5.3 真偽値のリスト [Bool] を 2 進数と見なして、対応する整数を計算する
関数 fromBin :: [Bool] -> Integer を定義せよ。例えば 、fromBin [True,
True] は 3, fromBin [True, False, True, False] は 10 になる。
ヒント : 引数の数を一つ増やした補助関数が必要になる。
ヒント : ホーナーの方法を使う。例えば fromBin [True, False, True, False]は ((1 × 2 + 0) × 2 + 1) × 2 + 0 fromBin [True, True, False, True] は ((1 × 2 +1) × 2 + 0) × 2 + 1 となるように計算する。
問 3.5.4 真偽値のリスト [Bool] を 2 進数と見なして、対応する整数を計算する関数 fromBinRev :: [Bool] -> Integer を定義せよ。ただし、先の問とは逆順に真偽値がならんでいると仮定せよ。例えば 、fronBinRev [True, True, False,
True] は 1 + 2 × (1 + 2 × (0 + 2 × 1)) = 11(10) となる。
問 3.5.5 実数のリスト xs と実数から実数への関数 f を受け取り、リストの各要
素に f を適用した結果の和を計算する関数 sumf :: [Double] -> (Double ->Double) -> Double を定義せよ。
問 3.5.6 2 つの引数 x, xs を受け取り、リスト xs から x と等しい要素を

1. もっと も 先 頭に 現れ る 一 つ の 要 素だ け 取 り 除 い た リ スト を 返 す 関 数
deleteOne
2. すべて取り除いたリストを返す関数 deleteAllをそれぞれ定義せよ。
問 3.5.7 リストを昇ベキの順に表された多項式と見なし 、多項式の値を計算する関数
evalPoly :: [Double] -> Double -> Double を 定 義 せ よ 。例 え ば 、[1, 2, 3, 4] とい うリスト は 1 + 2x + 3x2 + 4x3 とい う多項式と 見なし 、
evalPoly [1, 2, 3, 4] 10 の値は 4321 になる。

3.6

帰納法による証明

プログラミング言語の意味をラムダ計算や関数型言語で表現することの利点は、プログラムの同値性（等価性）などの議論が容易になるというところにある。
（これに対して例えば C 言語では 、c = getchar(); という代入文があったとしても、c の出現を getchar() で置き換えることはできない。）ここでは、そのような議論の例として、2 つのリストに関する関数が等価であることの証明を取り上げる。このような証明は帰納法と併用することが多い。以下の例も帰納法を使用している。
リストを反転する関数 reverse:

III - 11

1
2
3
4
5
6
7
8
9

-- append は Prelude の (++) 演算子と同じ
append:: [a] -> [a] -> [a]append [] ys= ysappend (x:xs) ys = x : (append xs ys)-- reverse は Prelude に定義済み
reverse:: [a] -> [a]reverse []= []reverse (x:xs) = append (reverse xs) [x]は上の定義では、引数の効率が悪い。
そこで次のような定義を考える。

1
2
3
4
5
6
7

に比例する時間がかかるために-- shunt は rev の補助関数
shunt:: [a] -> [a] -> [a]shunt ys []= ysshunt ys (x:xs) = shunt (x:ys) xs
rev:: [a] -> [a]rev xs = shunt [] xs
この rev という関数は、引数のに比例する時間でリストを反転できるので効率が良い。
rev と reverse が等価であること – 正確に言うと、すべての有限リスト xs に対して

rev xs = reverse xsが成り立つことを証明できる。
そのためには、次のような補助定理を証明すれば良い。

shunt ys xs = append (reverse xs) ys
これは、
証明:

で証明することができる。

xs = [] のとき:

xs = z:zs のとき:

III - 12

問 3.6.1 すべての有限リスト xs について、

1. append xs [] = xs
2. append xs (append ys zs) = append (append xs ys) zsが成り立つことを、xs に関する帰納法で証明せよ。

3.7

有用なリスト 処理関数

次のようなリストに対する関数がよく利用される。これらは Prelude（標準ライブラリ）に定義済みである。
これらのリスト処理関数の多くは高階関数である。
高階関数とは、関数を引数としたり、関数を生成して戻り値とするような関数のことである。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

map :: (a -> b) -> [a] -> [b]map f []
= []map f (x:xs) = f x : map f xs
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]zipWith f (x:xs) (y:ys) = f x y : zipWith xs ys
zipWith f __= []filter :: (a -> Bool) -> [a] -> [a]filter p []= []filter p (x:xs) = if p x then x : filter p xs else filter p xs
iterate :: (a -> a) -> a -> [a]iterate f x = x : iterate f (f x)
III - 13

15
16
17
18
19
20
21
22
23
24
25
26

foldr :: (a -> b -> b) -> b -> [a] -> bfoldr f x []= xfoldr f x (y:ys) = f y (foldr f x ys)
foldl :: (a -> b -> a) -> a -> [b] -> afoldl f x []= xfoldl f x (y:ys) = foldl (f x y) ys
concat :: [[a]] -> [a]concat []= []concat (xs:xss) = xs ++ concat xss

問 3.7.1 これらの関数（や以前に紹介した関数）を使って、次のような関数を定義せよ。

1. 2 つのリストの 0 番目の要素同士、1 番目の要素同士、. . . を比較し 、等しい要素の個数を返す関数 countEq
例えば countEq [1,2,3,5] [2,2,6,5,3] は 2 になる。
2. 文字列のリストを受け取り、各文字列の最後に “;” をつけて連接した文字列を返す addSemicolon
例えば addSemicolon ["abc", "xyz", "123"] は "abc;xyz;123;"になる。

3.8関数の中置記法化

Haskell の関数は通常は前置記法で用いるが 、識別子を “ ”（バッククォート、
クォート（ “’” ）ではないことに注意）で囲むことによって、中置記法で書くことができる。これは小さなことに見えるが実は意外に便利である。例えば 、次のよ
うに Prelude で定義された zip の場合、
123

zip :: [a] -> [b] -> [(a,b)]zip (a:as) (b:bs) = (a,b) : zip as bs
zip _
_
= []

III - 14

通常は zip [1,2] [3,4] のように書くが、これを [1,2] ‘zip‘ [3,4] と書いても良い。

Q 3.8.1 append [1,2] [3,4,5] を ‘〜‘ を使って中置記法で書け。
中置記法で用いる演算子に対して、infixl, infixr, infix などのキーワードを使って、優先順位と結合性を定めることができる。たとえば 、Prelude（ Haskellにはじめから読み込まれる標準ライブラリ）では次のように宣言されている。

1
2
3
4
5
6
7
8
9
10
11
12
13

infixr 9
infixl 9
infixr 8
infixl 7
infixl 6
infixr 5
infixr 5
infix 4infixr 3
infixr 2
infixl 1
infixr 1
infixr 0.
!!
ˆ, ˆˆ, ***, /, ‘quot‘, ‘rem‘, ‘div‘, ‘mod‘, :%, %+, :++==, /=, <, <=, >=, >, ‘elem‘, ‘notElem‘&&||>>, >>==<<$, $!, ‘seq‘

infixl は、infixr はを表す。ただの infix はど ちらでもないこと（非結合—例えば 1 < x < 2 は構文エラー！）を表す。また、2 列目の数字が大きいほど 、優先順位が高い。例えば *は +よりも結合力が強い。
Q 3.8.2 次の式の解釈はど うなるか？括弧を挿入して演算順を明示的にせよ。
1.
x ‘rem‘ 3 /= 1
2.
xs !! 9 : ys ++ zs
バッククォートと逆に本来中置記法で使用される演算子を “(” と “)” でくくって、ふつうの前置記法で用いることができる。例えば 1+2 を (+) 1 2 と書くことができる。あるいは関数の引数として渡すこともできる。

Q 3.8.3 次の式を通常の中置記法で書け。
1.
(+) ((*) 2 x) 1
2.
(++) xs ((++) ys zs)

3.9 部分適用とセクション
Haskell の関数はカリー化されている。すなわち、 多引数の関数は「関数を返す関数」として表現されている。引数の一部だけを適用して、結果の関数を mapのような関数の引数に使うことは良くある。
Prelude> map (take 2) [[1,2,3],[4,5,6,7],[8,9,10]][[1,2],[4,5],[8,9]]Prelude> map (zip [8,7,6]) [[1,2,3],[4,5,6,7],[8,9]][[(8,1),(7,2),(6,3)],[(8,4),(7,5),(6,6)],[(8,8),(7,9)]]}III - 15

Haskell では演算子にも部分適用ができるようになっている。例えば (2*) は 2倍する関数。(/2) は 2 で割る関数である。このような二項演算子の部分適用をセクションという。
Prelude> map (2*) [1,2,3][2,4,6]Prelude> map (/2) [1,2,3][0.5,1.0,1.5]
Prelude> map (1/) [1,2,3][1.0,0.5,0.3333333333333333]}

Q 3.9.1 次のセクションをラムダ式で書け。
1.
(xs++)
2.
(!!9)
ただし “-” 演算子は、単項演算子の “-” も存在するので、(-2) はセクションにはならない。その代わり subtract という関数（ subtract x y = y - x ）が存在するので、subtract 2 と書くことができる。

3.10 局所的定義
let というキーワード を用いて、局所的な変数を定義することができる。
let （ 複数の）変数の定義 in 式という形で用いる。

1234

pow4 x = let y = x*x in y*y-- head は Prelude に定義済み
head ys = let (x:xs) = ys in x-- head (x:xs) = x と定義することもできるなどである。

Q 3.10.1 次のような関数を let を用いて定義せよ。
1. 27 乗する関数 pow27
2. リストの尾部（ 頭部を除いた残り）を求める関数 tail
この例では 4 乗する関数（ pow4 ）を定義しているが 、y*y の部分が変数 y の有効範囲（）に属している。実は、さらに “変数の定義” の右辺の部分（この例では、

123の部分）もスコープに属している。これは次の例でわかる。

-- repeat は Prelude に定義済み
repeat :: a -> [a]repeat x = let xs = x:xs in xs
この関数は要素 x の無限リストを生成する。

III - 16

Prelude> repeat 1[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, . . . 4（このような定義は 、Haskell では “止まらない・役に立たない式” ではなく、意
味のある式となる。このことは、あとで Haskell の評価戦略を紹介する時に説明する。）

Q 3.10.2 repeatList [1,2,3] が [1,2,3,1,2,3,1,2,3, . . . ] という無限リス
トになるような関数 repeatList :: [a] -> [a] を定義せよ。
問 3.10.3 リストを集合だと見なして、そのベキ集合（部分集合の集合）を返す関
数 powerset を定義せよ。
例えば powerset [1, 2, 3] は [[], [1], [2], [3], [1, 2], [2, 3],[1, 3], [1, 2, 3]] になる。
（ただし 、順番はこの通りでなくても良い。）
ヒント : セクションを使うと簡潔に定義できる。
（ 発展）where 節 where というキーワード を使うと、関数定義の右辺で使用される変数・関数を後ろに局所的に定義することが出来る。
関数名 パターンの並び = 式
where （ 複数の）変数の定義という形で用いる。
（この形式では示されていないが 、局所的定義された変数が複数のガード 節にまたがって使用されていてもよい）上記の pow4, head は次のよ
うに定義することも出来る。

1
2
3
4
5

pow4 x = y*ywhere y = x*x-- head は Prelude に定義済み
head ys = x
where (x:xs) = ys

3.11 代数的データ型の定義
リストのようなデータ型をプログラマがあらたに定義する方法も用意されている。このようなデータ型は複数のを持つことができる。このようなデー
タ型を（ algebraic datatype ）という。
データ型の宣言の一般的な形式は次のとおりである。

data 型構成子名 型引数 1 型引数 2 . . .
= 構成子名 1 型 1,1 . . . 型 1,n1
| 構成子名 2 型 2,1 . . . 型 2,n2
| ...
| 構成子名 m 型 m,1 . . . 型 m,nm
4

Ctrl-c で中断する。

III - 17型引数 k型構成子名・構成子名ともに使える文字は変数名の場合と同じだが 、変数名とは逆にから始まる必要がある。
代数的データ型は構成子にパラメータがない場合は、C や Java の列挙（ enum ）型と同じようなものである。次の例では、

12data Direction = North | South | West | East
deriving (Eq, Ord, Show)
North, South, West, East の 4 つがが Direction 型を構成している。
（ deriving. . . については後述する。）
Q 3.11.1 じゃんけんの３つの手（グー・チョキ・パー）を表すデータ型 RPS を定義せよ。
一般的には代数的データ型の構成子はパラメータを持つ。次の例は二分木を表すデータ型を定義している。

12

data Tree a = Empty | Branch (Tree a) a (Tree a)deriving (Eq, Ord, Show)
このデータ型は Branch と Empty の 2 つの構成子を持つ。Empty は引数を取らず、それだけで二分木を構成する。Branch は 3 つのフィールド を持つ。1 番目と 3 番
目は自分自身と同じ型の二分木であり、2 番目は要素である。つまり、Branch は
次のような型を持っている。

Branch ::ここで、a はであり、ここには Integer や String など の具体化な型がはいることができる。例えば Tree Integer は要素が Integer 型であるような二分木の型である。Tree 自体は型ではなく型構成子 (type constructor) である。つまり、型パラメータを伴ってはじめて型になる。
具体的には次のような式がこの Tree 型を持つ。

1
2
3
4
5
6
7
8
9
10

tree1 :: Tree atree1 = Empty
tree2 :: Tree Integer
tree2 = Branch Empty 1 Empty
tree3 :: Tree String
tree3 = Branch (Branch Empty "a" Empty)"b" (Branch Empty "c" Empty)
tree4 :: Tree Integer
tree4 = Branch (Branch Empty 1 Empty)
2 (Branch Empty 3 (Branch Empty 4 Empty))
例えば tree4 の構造は、図で表すと次のようになる。
???


1



2 ??

?

3 ??

?

III - 18

4

Tree 型に対する関数は、パターンマッチングを用いて、次のように定義することができる。
123456

top :: Tree a -> a
top (Branch _ a _) = a
isEmpty :: Tree a -> BoolisEmpty Empty = True
isEmpty _= False問 3.11.2 Tree 型に対して、次のような関数を定義せよ。

size:: Tree a -> Integer -- 要素数
depth:: Tree a -> Integer -- 深さ
preorder :: Tree a -> [a]-- 前順走査inorder:: Tree a -> [a]-- 中順走査postorder :: Tree a -> [a]-- 後順走査reflect:: Tree a -> Tree a -- 鏡像
例えば、1 size tree4, 2 depth tree4, 3 preorder tree4, 4 inorder tree4,
5 postorder tree4, 6 reflect tree4 の結果はそれぞれ 、 1 4, 2 3, 3
[2,1,3,4], 4 [1,2,3,4], 5 [1,4,3,2], 6 Branch (Branch (Branch Empty
4 Empty) 3 Empty) 2 (Branch Empty 1 Empty) となる。
問 3.11.3 一般の n 分木（任意の個数の子を持つことができる木）を表すデータ型を定義せよ。
問 3.11.4 PL/0 (http://www.inf.ethz.ch/personal/wirth/books/AlgorighmE0)の構文木を表すデータ型を定義せよ。
（発展） フィールド ラベル C の構造体のように代数的データ型の各フィールドに名前（フィールド ラベル ）をつけることも可能である。

data C = F { f1, f2 :: Int, f3 :: Bool } deriving (Eq, Ord, Show)
この宣言は、次の宣言と同等のデータ型を定義する。

data C = F Int Int Bool deriving (Eq, Ord, Show)
さらに、フィールド ラベルは新しいデータを構築するときにも、パターンマッ
チングにも使用することが出来る。いずれもコンストラクタの後に、ブレース内に “フィールド ラベル = 式” のコンマ区切りの並びを書く。

1
2
3
4

v1 = F { f1 = 5, f2 = 12, f3 = False }foo :: C -> Int
foo (F { f1 = x, f2 = y }) = x*x + y*y

III - 19

このとき foo v1 の値は 169 になる
またフィールド ラベルは、データからフィールド の値を取り出す関数として使用することが出来る。例えば 、上で定義された v1 に対して、f1 v1 の値は 5 になる。
式の後に、“フィールド ラベル = 式” のコンマ区切りの並びをブレース内に書いて、指定したフィールドの値のみを変更した新しいデータを構成するときにも使用できる。v1 { f2 = 3 } の値は F { f1 = 5, f2 = 3, f3 = False }になる。

3.12

Haskell の評価戦略

Haskell の式の評価は、ラムダ計算と同じく β 変換に基づいている。つまり、(\
x -> M ) N という部分式を、関数の戻り値 M のなかの 仮引数 x の自由な出現を
実引数 N に置き換えた式に書き換える。例えば 、“(\ x -> x+2) 3” を 3+2 に置き換える。
これ以上 β 変換ができない式を正規形という。
一つの式に幾通りもの β 変換が可能なことがある。このとき、異なる β 変換を選ぶと、評価の結果が別の形に枝分かれしてしまう。




β

M?

?? β
??
?

M1
M2
しかし 、うまく何回か β 変換を行なうと、この枝分かれしたものを再び合流させられることが知られている。
（チャーチ・ロッサーの定理）
M1 ?

??
?
β ?

M0

M2




 β

これは同時に、ある式に正規形が存在するならば 、それは一つしかない（ α 変換による違いを除く）ということを保証している。
ラムダ計算のところでも紹介したが、最も左からはじまる β 基を選んでいけば 、正規形の存在する式ならば 、必ず正規形に到達することが可能であるということが知られている。この評価戦略をという
Haskell の評価戦略は、基本的にこの最左戦略による評価方法である。つまり正規形を持つ式の評価は必ず止まる。ただし 、内部的にはを用いる
点がラムダ計算の場合と異なる。
例えば 、次のように定義された twice という関数を考える。

twice x = x*x
最左戦略では twice (2+2) という式は次のように計算することになる。

twice (2 + 2) = (2 + 2) ∗ (2 + 2)
= 4∗4
= 16
III - 20

つまり、twice の引数である (2+2) は計算されないまま、まず twice の定義にしたがって式が展開される。そして、本当に必要になって (この場合は *の引数だから必要) はじめて 2+2 が計算される。この方式をナイーブに実行すると、2+2 が二度計算されてしまう。
グラフ簡約では、このような計算をグラフの形で表して、2+2 を一度しか計算しないようにしている。

twice




2



*

−→

+?

?

2

2


+?
?



*

−→


−→

4

2

最左戦略は必要になるまで評価を遅らせるので（ lazy evaluation ）とも言われる。ただし 、プログラミング言語で遅延評価を用いる場合は、このようにグラフ簡約と組み合わせて、同じ計算の繰り返しを避けるようにするのが一般的である。
遅延評価の良いところは概念的に無限の大きさのデータ構造を扱えることである。例えば次のような関数を考える。

1
2
3
4
5
6
7
8

from :: Integer -> [Integer]from n = n : from (n+1)-- take は Prelude に定義済み
take :: Integer -> [a] -> [a]take 0 _= []take _ []= []take n (x:xs) = x : take (n-1) xs
すると from 1 は [1, 2, 3, . . . ] という無限リストだが、この無限リストを途中で用いている take 3 (from 1)という式はtake 3 (from 1) → take 3 (1:from (1+1))→ 1:(take 2 (from (1+1))) → 1:(take 2 ((1+1):from (1+1+1)))→ 1:(1+1):(take 1 (from (1+1+1)))→ · · · → 1:(1+1):(1+1+1):(take 0 (from (1+1+1+1)))→ 1:(1+1):(1+1+1):[] (= [1,2,3])のように有限時間で計算できる。
なお、from で生成されるような等差数列については “..” を使った略記法（ 糖衣構文）がいくつか用意されている。

Prelude> [1..][1,2,3,4,5,6,7,8,9,10,11, . . .
Prelude> [2,4..][2,4,6,8,10,12,14,16,18,20,22, . . .
Prelude> [1..10][1,2,3,4,5,6,7,8,9,10]
Prelude> [1,4..20]
III - 2116

[1,4,7,10,13,16,19]（ 発展） “..” の翻訳
これらは単に Prelude で定義された関数の呼出しに翻訳される。
[ e1 .. ]= enumFrom e1[ e1 , e2 .. ]= enumFromThen e1 e2[ e1 .. e2 ]= enumFromTo e1 e2[ e1 , e2 .. e3 ] = enumFromThenTo e1 e2 e3
遅延評価を用いるといろいろと興味深いプログラミングが可能になる。参考文
献 [6] は、遅延評価を利用したプログラムの部品化の手法を詳しく説明している。
一方、遅延評価を用いるとプログラムの各部分がどのような順序で実行されるのか、事前に推測することが難しい。遅延評価を用いるためには、副作用が存在しないことが大前提である。
問 3.12.1 take の反対に、リストの最初の n 個の要素を取り除く関数 myDrop ::Integer -> [a] -> [a] を定義せよ。
問 3.12.2 fib をフィボナッチ数列の無限リストとして定義せよ。
ヒント : フィボナッチ数列同士をずらして足し算すると . . .

1
+)

1

1
1
2

2
1
3

3
2
5

5
3
8

8 ...
5 ...
13 . . .

ヒント : zipWith を使う。
問 3.12.3 要素に重複のない昇順に並んだ 2 つのリストをマージして、やはり重複なしの昇順のリストを生成する関数 merge を定義せよ。
問 3.12.4 2i · 3 j · 5k（ i, j, k は 0 以上の整数）の形で表せる整数のみを重複なしに昇順に並べたリスト hamming を定義せよ。このリストの 699 番目の要素（ただし最初を 0 番目と数えた場合）が 5898240 であることを確認せよ。
ヒント : map と 問 3.12.3 の merge を使う。
問 3.12.5 Haskell 以外の言語で、無限リストをシミュレートする方法を考察せよ。
またそれを用いて、素数列を生成せよ。

3.13 リスト の内包表記 （ List Comprehension ）（ list comprehension ）という糖衣構文（ syntax
Haskell は、リストのsugar ）を持つ。これは数学で使われる集合の内包表記に似た記法である。

III - 22

例

Prelude> [(x, y) | x <- [1, 2, 3, 4], y <- [5, 6, 7]][(1,5),(1,6),(1,7),(2,5),(2,6),(2,7),(3,5),(3,6),(3,7),.
(4,5),(4,6),(4,7)]
Prelude> [x*x | x <- [1..10], odd x][1,9,25,49,81]
ただし [1..10] は [1,2,3,4,5,6,7,8,9,10] の略記法である。また、. は、本
当は改行しない（プリントの幅の都合で改行している）ことを示している。
リストの内包記法は次のような形のものである。

[ 式 | 限定式, . . . , 限定式 ]ここで限定式は、Bool 型の式（ガード ）か、次の形（ 生成式）:
変数（ 一般にはパターン ） <- 式のいずれかである。生成式の左辺の変数のスコープは、それより後の限定式である。生成式で変数に右辺の式を評価して得られるリストの要素を順に代入し 、ガー
ド で真となるもののみ抽出して、すべての組み合わせを列挙する。

Q 3.13.1 次の内容表記の値は何か ?
1. [ x*y | x <- [1, 2], y <- [3, 5, 7] ]2. [ (x, y) | x <- [1, 4, 7], y <- [2, 5, 8] , x < y ]問 3.13.2 非負の整数 n を受け取り、0 ≤ x ≤ y ≤ n となるすべての x, y の組を生成する関数 foo :: Integer -> [(Integer, Integer)] を内包表記を用いて定義せよ。
ヒント : .. を使う。
問 3.13.3 非負の整数 n を受け取り、1 ≤ x < y < z ≤ n の範囲で x2 + y2 = z2 とな
るすべての x, y, z の組を生成する関数 chokkaku :: Integer -> [(Integer,
Integer, Integer)] を 内包表記を 用いて 定義せ よ 。例えば 、chokkaku 20の値は、[(3,4,5),(6,8,10),(5,12,13),(9,12,15),(8,15,17),(12,16,20)]となる。
（ 順番はこの例と異なっていても良い。）
内包表記の翻訳
ができる。

1
2
3
4
5
6

リストの内包表記は次のような高階関数を用いて翻訳すること

unit :: a -> [a]unit a = a : []-- 要素数 1 のリストを返す

bind :: [a] -> (a -> [b]) -> [b]bind []_ = []
bind (x:xs) f = append (f x) (bind xs f)

III - 23

翻訳規則は次のとおりである。
（ 下線部に翻訳規則を再帰的に適用していく。）[t | ] ⇒ unit t[t | x <- u, P] ⇒ bind u (\ x -> [t | P])[t | b, P] ⇒ if b then [t | P] else [][t | let decls, Q] ⇒ let decls in [t | Q]
ただし 、b は Bool 値の式、P は限定式の並びである。例えば 、[(x,y) | x <- [1..3], y <- [2..4], odd (x+y) ]は次のように翻訳される。

⇒ bind [1..3] (\ x -> [(x,y) | y <- [2..4], odd (x+y) ])⇒ bind [1..3] (\ x ->bind [2..4] (\ y -> [(x,y) | odd (x+y) ]))⇒ bind [1..3] (\ x ->bind [2..4] (\ y -> if odd (x+y) then [(x,y) |] else []))⇒ bind [1..3] (\ x ->bind [2..4] (\ y -> if odd (x+y) then unit (x,y) else []))
内包表記を用いると、クイックソートは次のように簡潔に表される。

1
2
3
4

qsort []
= []qsort (x:xs) =qsort [ y | y <- xs, y < x]++ x : qsort [ y | y <- xs, y >= x]

問 3.13.4 次の内包記法を上の翻訳規則を用いて、unit, bind を用いた形にせよ。

1. [ (x, y) | x <- [1, 2, 3, 4], y <- [5, 6, 7] ]2. [ x*x | x <- [1..10], odd x ]問 3.13.5 primes を素数列 [2, 3, 5, 7, 11, . . . ] の無限リストとして定義せよ。
（ 内包表記を用いても、用いなくても良い。）
考え方: “エラトステネス (Eratosthenes) のふるい” というアルゴ リズムを実装する。このおなじみのアルゴ リズムを言葉で表現すると次のようになる。

1. 2 以上の自然数を並べる。
2. 先頭の数を取り除き、その倍数を同時にとり除く。
（この処理を “ふるい”(sieve) と呼んでいる。）
3. 2 を繰り返す。

III - 24

この時に先頭に現れた数を順番に並べたものが素数の列である。途中で無限リス
トの無限リストが現われるが 、問題ない。
このようにして、素数を無限リストとして表現することで、さまざ まな “境界条件” に対応することができる。C などで実装しようとすると、1000 までの素数というのは配列を用いて簡単に求めることができるが 、最初の 100 個の素数を求めるのは急に難しくなる。

問 3.13.6 他の言語で “エラトステネスのふるい” を実装してみよ。

3.14 8 クイーンの問題
リストの内包表記を用いて、有名なパズルを解いてみることにする。
8 クイーンの問題は 8 個のクイーンを、お互いにとることができないように 、チェス盤の上に置くという問題である。クイーンは縦・横・斜めのすべての方向に、何マスでも移動できる。この問題の可能な解はいくつか存在する。この可能な解の集まりをリストとして表現する。ここでは無限リストは本質的には使用しないが 、遅延評価は効率の点で決定的な役割を果たす。
クイーンの配置は、ここでは数のリストで表す。[4, 6, 1, 5, 2, 8, 3, 7]は次のような配置を表す。

III - 25

safe p n は、length p 列までのクイーンの配置が p というリストで与えられた時、第 length p + 1 列の第 n 行にクイーンを置くことができるかど うかを示
す関数である。
12345safe p n =all not [ check (i, j) (1+length p, n)| (i, j) <- zip [1..] p ]check (i,j) (m,n) = j==n || (i+j==m+n) || (i-j==m-n)ここで、all は

1
2
3

all
all p []
all p (x:xs):: (a -> Bool) -> [a] -> Bool
= True= if p x then all p xs else Falseと定義された標準ライブラリの関数である。[1..] は [1, 2, 3, . . . ] という無限リストの略記法である。

Q 3.14.1
1. all odd [1,3,5] の値は何か ?
2. all (>1) [2,0,3] の値は何か ?
> safe [1,3] 5
True> safe [1,3] 2
False
となる。

III - 26

Q 3.14.2
1. safe [1,4] 2 の値は何か ?
2. safe [1,5] 3 の値は何か ?
順に、最初の m 列のすべての安全な配置を調べていく、そのために、そのようなすべての配置 (のリスト ) を返す queens という関数を定義する。

1
2
3

queens 0
queens m= [[]]= [ append p [n]| p<-queens (m-1), n<-[1..8], safe p n ]例えば> queens 1[[1],[2],[3],[4],[5],[6],[7],[8]]}> queens 2[[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[2,4],[2,5],[2,6],[2,7],.
[2,8],[3,1],[3,5],[3,6],[3,7],[3,8],[4,1],[4,2],[4,6],[4,7],.
[4,8],[5,1],[5,2],[5,3],[5,7],[5,8],[6,1],[6,2],[6,3],[6,4],.
[6,8],[7,1],[7,2],[7,3],[7,4],[7,5],[8,1],[8,2],[8,3],[8,4],.
[8,5],[8,6]]となる。そうすると head (queens 8) で最初の解を求めることができる。

> head (queens 8)[1,5,8,6,3,7,2,4]
遅延評価を用いているので、最初の解を求めるためには本当に必要な部分の簡約しか行なわない。つまり、上の [1,5,8,6,3,7,2,4] を求めるのに、 queens 7 の計算をすべて行なっているわけではなく、この最初の解を求めるのに必要なだけの部分の計算をしている。これは、queens 7 を完全に計算させると head (queens8) よりも計算に時間がかかることからもわかる。ここでは、遅延評価は Prolog でいうところの後戻り (バックト ラック、 backtrack) と同じような効果を実現する。
つまり、1 つだけ解を求める計算とすべての解を求める計算を別々に記述する必要はなく、しかも、1 つだけ解を求めるためには、それに必要なだけの計算しか行なわない
ちなみに queens 8 を計算させると、

III - 27

> queens 8[[1,5,8,6,3,7,2,4],[1,6,8,3,7,4,2,5],(略),[8,3,1,6,2,5,7,4],[8,4,1,3,6,2,7,5]]
解はすべてで 92 個あることがわかる。
問 3.14.3 他の言語で、8 クイーンを実装せよ。可能ならば 、後戻りをシミュレー
トして、一つの解、すべての解をおなじプログラムで効率良く求められるようにせよ。

問 3.14.4 （ナイト巡回）ナイトは 、右の図の中央のマスから○印のマスへ移動できるチェスのコマである。5 × 5 マスのチェス盤で、あるマス（例
えば 、左上隅）から始めてすべてのマスを 1 回ず
つ訪れる経路を求めるプログラムを作成せよ。
問 3.14.5 （アガリ判定）

1. ソートされた整数のリストのなかで、3 つ並びの数、2 つの同じ数を見つけてリストアップする関数 shuntsu, toitsu をそれぞれ定義せよ。
Prelude> shuntsu [1,3,3,4,5,7,8,9][[3,4,5],[7,8,9]]Prelude> toitsu [1,3,3,4,5,7,7,9][[3,3],[7,7]]
2. 14 個の要素を持つ Int のソートされたリストがマージャンの清一色（チンイーソー）のアガ リ形になっているかを判定する関数 chinitsu を定義せよ。ただし 、アガリ形とは、順子（ 3 つ並びの数）または刻子（ 3 つの同じ数）が 4 つ、対子（ 2 つの同じ数）が 1 つ、そろった形である。

ᛗᛗᛗᛘᛙᛚᛛᛛᛜᛝᛞᛟᛟᛟ
้Ꮚ

㡰Ꮚ

ᑐᏊ

㡰Ꮚ

้Ꮚ

3.15 さらに詳し く知りたい人のために . . .
文献 [1] は、Haskell に関するもっとも主要な情報源である。文献 [2] は日本語での Haskell の主要な情報源である。文献 [3] は Haskell の仕様書、Haskell を利用すIII - 28

る上での基本ドキュメントである。文献 [4] は、もうひとつの Haskell のメジャーな処理系 Hugs のユーザーマニュアルである。文献 [5] は、Haskell の実装について知りたい人にお勧めする。文献 [6] は、遅延評価を実際のプログラムでどのように用いるかを解説している。文献 [7] はリストの内包表記を解説している。文
献 [8] は、情報処理学会の会誌「情報処理」に 2005 年 4 月から 2006 年 3 月まで連載された Haskell に関する記事である。文献 [9] は Haskell を設計した中心人物の一人による Haskell の設計の “回顧”（と “展望” ）である。文献 [10] は Haskell
でなく、Miranda という言語を使っているが関数プログラミングに関する、とても有名な良書である。文献 [11, 12, 13] は日本語の初級者向けの解説書である。

この章の参考文献[1] 「 Haskell – A Purely Functional Language featuring static typing, higherorder functions, polymorphism, type classes and monadic eﬀects 」http://www.
haskell.org/[2] 「 Programming in Haskell 」http://www.sampou.org/cgi-bin/haskell.
cgi[3] Simon Peyton Jones, John Hughes 他「 Haskell 98: A Non-strict, Purely Functional Language 」
1999 年 2 月, http://www.haskell.org/onlinereport/[4] Mark P Jones, Alastair Reid 他「 The Hugs 98 User Manual 」
http://cvs.haskell.org/Hugs/pages/hugsman/[5] Simon Peyton Jones, David Lester 「 Implementing Functional Languages 」
Prentice Hall, 1992 年
http://research.microsoft.com/Users/simonpj/Papers/pj-lester-book/[6] John Hughes 「 Why Functional Programming Matters 」
1989 年, http://www.md.chalmers.se/˜rjmh/Papers/whyfp.html
日本語訳 – 山下 伸夫 訳 「なぜ関数プログラミングは重要か」
http://www.sampou.org/haskell/article/whyfp.html[7] Philip Wadler 「 List Comprehensions 」（ Simon Peyton Jones 「 The Implementation of Functional Programming
Languages 」
Prentice Hall, 1987 年
http://research.microsoft.com/users/simonpj/Papers/slpj-book-1987/のなかの第 7 章）
[8] 和田 英一 他 「 Haskell プログラミング 」
http://www.ipsj.or.jp/07editj/promenade/III - 29[9] Simon Peyton Jones 「 Wearing the hair shirt – A retrospective on Haskell 」
2003 年, http://research.microsoft.com/∼simonpj/papers/haskell%
2Dretrospective/[10] Richard Bird, Philip Wadler 著 武市 正人 訳 「関数プログラミング 」
近代科学社, 1991 年 4 月, ISBN4-7649-0181-1[11] 向井 淳 「入門 Haskell はじめて学ぶ関数型言語」
毎日コミュニケーションズ , 2006 年 3 月, ISBN4-8399-1962-3[12] 山下 伸夫 （ 監） 青木 峰郎 （ 著）
「ふつうの Haskell プログラミング ふつうのプログラマのための関数型言語入門」
ソフトバンク クリエイティブ , 2006 年 6 月, ISBN4-7973-3602-1[13] Graham Hutton 著 山本 和彦 訳 「プログラミング Haskell 」
オーム社, 2009 年 11 月, ISBN978-4-274-66781-5

III - 30