第2章

関数型言語 Haskell とは（空欄 2.0.1）
Haskell はと呼ばれ、ラムダ計算を基本としながら実際の使用に便利な機能を追加したプログラミング言語である。
他のプログラミング言語と比べた時の特徴は、以下のようになる。

1.

（空欄 2.0.2）

されている。つまり、コンパイル時に（実行する前に）型エラーが検出される。
（空欄 2.0.3）を持ち、プログラマがメモリの管理に煩わされること

2.
がない。

3. 関数を他の関数の引数としたり、関数を生成して他の関数の戻り値とした（空欄 2.0.4）
り、関数を一般の値として使うことができる（）。
4. 多相型を許すことにより、汎用性のある関数を定義することができる。
5. 代数的データ型というユーザー定義のデータ型を定義することができる。
6. 代数的データ型に対してパターンマッチングによる場合分けで処理を定義することができる。
7. 型推論により、（ほとんどの場合）プログラム中に型を書く必要はない。また、型クラスなど、型システムが発達している。
（空欄 2.0.5）
8. 式にはない。入出力や参照の書換えなどの効果も値として表現される。このため、プログラムの同値性などの性質に関する考察が、より容易になる。

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

2.1 Haskell 処理系の入手とインストール
Haskell の環境としてここでは Haskell Platform を利用することにする。Haskell
Platform は Haskell 処理系の GHC (Glasgow Haskell Compiler1 ) に標準的なツー
1

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

II - 1

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

2.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（このテキスト中の実行例では、3 のように斜体になっているところがシステムの出力で、それ以外がユーザの入力である。暴走したときは、Ctrl-c で中断できる。）（空欄 2.2.1）
Haskell のプログラムソースファイルには通常という拡張子をつける。

II - 2

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

II - 3

変数名 1 = 式 1
変数名 2 = 式 2...
変数名 n = 式 n関数定義関数を定義するときは、仮引数を “=” の左辺に並べて、trivial x = x
twice x
= 2*x
foo x y= 2*x+yのように書くことができる。関数 trivial や関数 twice の場合は、x が、関数
foo の場合は x と y が仮引数である。
これらは、C ならば、

int trivial(int x) { return x; }int twice(int x) { return 2*x; }int foo(int x, int y) { return 2*x+y; }という関数に相当する。(Haskell では x, y が int 型という制限はないが、C ではこのように型の制限のない関数を定義することはできないので、便宜上 int 型にしている。)
四則演算の演算子は、C や Java と共通のものが多いが、割り算関係などは異なる。異なる点は必要になった時点で説明する。
関数の適用（呼出し）は “twice 2” や “foo 3 4” のように関数と実引数を並べて書くだけである。
（その値はそれぞれ、4 と 10 になる） 通常の数学の記法やC 言語などのように引数に括弧をつける必要はない。もちろん演算の順番を明示するために “foo (twice 2) (trivial 3)” のように括弧を使用することはできる。（この値は 11 になる。）

Q 2.3.1 次のような関数を定義せよ。
1. 3 倍して 1 を引く関数 bar
2. 3 乗する関数 cube

ラムダ式 Haskell では、無名関数を表すのにラムダ式というラムダ計算に由来する記法を用いる。
“ （空欄 2.3.1）”（バックスラッシュ）（ただし、日本語環境ではしばしば円マーク=” になってしまう）のあとに仮引数を空白で区切って並べて書き、そのあとに“Y

II - 4“ （空欄 2.3.2）”、つづけて関数本体の式を書く。例えば、“\ x y -> 2*x+y” は、
2 つの引数 x, y を受け取り、x の 2 倍と y の和を返す関数である。ラムダ式は無名関数（あるいは匿名関数）とも言う。
（ラムダ計算とは、 “λ” の代わりに “\” を、“.”（ピリオド） の代わりに “->”を用いる点が異なる。）
当然ながら、仮引数の名前は（他の変数と衝突しない限り）自由に選ぶことができる。例えば、“\ x y -> 2*x+y” と “\ dog cat -> 2*dog+cat” は同じ関数を表す。このような変数名の付け替えを α 変換と言う。
上記の関数定義は、次のラムダ式を使った定義とまったく等価である。
trivial = \ x -> x
twice
= \ x -> 2*x
foo= \ x y -> 2*x+y

ラムダ式の例

1. \ x -> x — これは x という引数を受け取って、 x をそのまま返すので、恒等関数を表している。C ならば、
int trivial(int x) { return x; }という関数 trivial に相当する。

2. \ x y -> x — これは、x と y という引数を受け取り、x を返す関数である。
C の記法では
int foo(int x, int y) { return x; }と表される 2 引数の関数に相当する。

Haskell は多引数関数と “関数を返す関数” とを同一視する。つまり、\ x y -> x
は、\ x -> (\ y -> x) と同等である。このように、多引数関数を “関数を返す関数”（空欄 2.3.3）
として表現することを、と言う。カリー (Curry) は、著
名な数理論理学者 Haskell B. Curry の名にちなんでいる。
\ x -> (\ y -> x) として見る場合、これは、 x という引数を受け取り、\ y -> x という関数を返す関数である。そして、\ y -> x という関数は、
y という引数を受け取り、（これを無視して） x を返す関数である。つまり、
式全体は高階関数である。
3. \ f x -> f (f x) — 関数 f とデータ x を受け取って、 f を x に 2 回適用する関数である。
Q 2.3.2 Q.2.3.1 の関数 bar, cube を、“変数 = ラムダ式” の形式で定義せよ。

II - 5

コメント

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

•（空欄 2.3.4）•

2.4というかたち（一行コメント）（空欄 2.3.5）というかたち（複数行コメント）

組み込みのデータ型と演算子

Haskell では真偽値（Bool）、整数（Int, Integer—Int は固定（有限）精度の整数, Integer は任意精度 2 の整数）、浮動小数点数（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)
関数適用は他のどんな中置記法の演算子よりも（空欄 2.4.1）。そ（空欄 2.4.2）のため、fact(n-1) は fact n-1 と書くことはできない。後者はの意味になってしまう。逆に n*(fact(n-1)) の外側の括弧は必要ない。
なお、この例のように変数は定義することが可能である。つまり、定義の右辺に自分自身を使用することができる。再帰的定義に特別な文法を使用する必要はない。

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

2

メモリが許す限り、いくらでも桁数を大きくとることができる。

II - 6

（発展）ガード ガードといって、仮引数の並びの後に “|” を書き、そのあとに条件式を書くことが出来る。ガード節（「| 条件式 = 右辺」のかたち）は複数個並べることが出来る。その場合、上（左）のガードから条件式を評価し、真になった箇所の “=” の右辺を評価する。ガードを使うと、上記の fact の定義は次のよ
うに書くことが出来る。

1
2

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

なお、otherwise は単に標準ライブラリで True と定義されている変数である。

Q 2.4.2 フィボナッチ数列

(n = 0, 1)
 an = 1 an = an−2 + an−1 (n ≥ 2)を計算する関数 fib を（効率を気にせず単純に）定義せよ。ただし、fib 0 = 1,
fib 1 = 1, fib 2 = 2, fib 3 = 3, fib 4 = 5, fib 5 = 8, . . . である。
注意: 定義を誤って処理系が暴走したら、通常 Ctrl-c で止めることができる。

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

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

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

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

Q 2.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
次の図のようになる。

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

箱ポインター記法

☆:△

☆ △

xs3

xs2 []

xs1

3

2

1

II - 8

また、[[1,2],[3,4]] というリストのリストはという箱ポインター記法（の左上の太い矢印）で表される。

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

[2,3,5,7,11]

2.

[[]]

3.

[0]

14. [[1],[2,3,4],[]]
2
5.

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 で表される。
C 言語でリストを扱う場合は、malloc で割り当てたメモリをいつ free をする
かを気を付けなければいけない。Haskell や他の関数型言語ではゴミ集めという仕II - 9

組みのおかげで明示的に free しなくても、いらなくなったメモリ領域は自動的に回収されることになっている。
組 組 (tuple) も 組 み 込 み の デ ー タ 型 と し て 用 意 さ れ て い る 。組 は 要 素 を“,”（ コ ン マ ）で 区 切って 並 べ 、 “(” と “)” で 囲 ん で 表 す。組 は リ ス ト の場 合 と 異 な り、要 素 の 型 が 同 一 で あ る 必 要 は な い 。(1,’a’) と い う 式 の 型はと表記される。また、(2,’b’,[3]) という式の型はと表記される 3 。

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

(’X’,("Aloha",False))() という要素がゼロ個の組もある。ユニット (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 はとともに多相型
このように型変数を含む型をを許す代表的なプログラミング言語である。
なお、変数の型をプログラム中に明示したい場合 “::” という記号を使って、変数名 :: 型と書く。例えば trivial や fact の型を明示しておきたい場合は、

3

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

II - 10

1
2
3
4
5

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

2.5

パターンマッチング

Haskell では、関数定義の仮引数の部分にというものを書いて、引4数の形に応じて場合分けを行なう事が可能である 。パターンとは、大雑把に言って変数と定数、構成子（:や [] など）からのみ生成される式である。
1
2
3
4
5
6
7
8

fact :: Integer -> Integer
fact 0 = 1
fact n = n * fact (n-1)-- Prelude の length とほぼ同じ
myLength :: [a] -> Integer
myLength []= 0
myLength (x:xs) = 1 + myLength xs
関数名 パターン 11 . . .
関数名 パターン 21 . . .
...
関数名 パターン n1 . . .

パターン 1m = 式 1
パターン 2m = 式 2パターン nm = 式 n

呼出し時には、関数定義の上から下の順に、関数の実引数をパターンと照合し、マッチした定義の右辺が評価される。この例の場合、myLength の引数が空リス
ト（[]）ならば 1 行目が選択される。一方、1 つ以上の要素を持つリストならば 2
行目が選択され、リストの先頭要素が変数 x に束縛され、残りのリストが変数 xsに束縛される。（なお、myLength とほとんど同じ関数 length :: [a] -> Intが標準ライブラリに用意されている。）
なお、GHC はパターンマッチングがすべての場合を尽くしていなくても通常
警告を出力しないが、コマンドラインオプション-fwarn-incomplete-patternsを指定することで警告を出すようにすることができる。
パターンマッチングで、右辺で使わない部分には “_”（アンダースコア）を使って変数に束縛せず、無視することができる。例えば myLength の場合、x は右辺で使用していないので、

myLength (_:xs) = 1 + myLength xs4

一般に関数型言語はデータの種類は増えずに処理（関数）が増えるような場合が得意、オブジェ
クト指向言語は、データ（クラス）の種類が増えて、処理（メソッド）が増えないような場合が得意である。

II - 11

と書くことができる。
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などである。この場合は、パターンは一種類のみで場合分けはできず、パターンにマッチしない引数が与えられればエラーとなる。
問 2.5.1 リスト中の数の和、積を求める関数 mySum, myProd を定義せよ。
（同等の関数 sum, product は標準ライブラリに用意されている。）
問 2.5.2
1. 真偽値のリスト [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 となるように計算する。

2. 真偽値のリスト [Bool] を 2 進数と見なして、対応する整数を計算する関数 fromBinRev :: [Bool] -> Integer を定義せよ。ただし、先の問とは逆順に真偽値がならんでいると仮定せよ。例えば、fronBinRev[True,True,False,True] は 1 + 2 × (1 + 2 × (0 + 2 × 1)) = 11(10) となる。
3. リストを昇ベキの順に表された多項式と見なし、多項式の値を計算する関数
evalPoly :: [Double] -> Double -> Double を 定 義 せ よ 。例 え ば 、[1,2,3,4] というリストは 1+2x+3x2 +4x3 という多項式と見なし、evalPoly[1,2,3,4] 10 の値は 4321 になる。
II - 12

問 2.5.3 実数のリスト xs と実数から実数への関数 f を受け取り、リストの各要
素に f を適用した結果の和を計算する関数 sumf :: [Double] -> (Double ->Double) -> Double を定義せよ。
問 2.5.4 2 つの引数 x, xs を受け取り、リスト xs から x と等しい要素を

1. もっと も 先 頭 に 現 れ る 一 つ の 要 素 だ け 取 り 除 い た リ ス ト を 返 す 関 数
deleteOne
2. すべて取り除いたリストを返す関数 deleteAllをそれぞれ定義せよ。

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

1
2
3
4
5
6
7
8
9

-- (++) は Prelude に定義済み(++):: [a] -> [a] -> [a][] ++ ys
= ys
(x:xs) ++ ys = x : (xs ++ ys)-- reverse は Prelude に定義済み
reverse:: [a] -> [a]reverse []= []reverse (x:xs) = (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 という関数は、引数のストを反転できるので効率が良い。

に比例する時間でリ

II - 13

rev と reverse が等価であること – 正確に言うと、すべての有限リスト xs に対して

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

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

ys

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

xs = [] のとき:

xs = z:zs のとき:

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

1. xs ++ [] = xs
2. xs ++ (ys ++ zs) = (xs ++ ys) ++ zsが成り立つことを、xs に関する帰納法で証明せよ。（どこで帰納法の仮定を使用するか明示せよ。）

II - 142.7

有用なリスト処理関数

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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 __= []take :: Integer -> [a] -> [a]take 0 _= []take _ []= []take n (x:xs) = x : take (n-1) xs
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)
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]II - 1530
31

concat []= []concat (xs:xss) = xs ++ concat xss

問 2.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;"になる。

2.8関数の中置記法化

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

zip :: [a] -> [b] -> [(a,b)]zip (a:as) (b:bs) = (a,b) : zip as bs
zip _
_
= []
通常は zip [1,2] [3,4] のように書くが、これを [1,2] ‘zip‘ [3,4] と書いても良い。
中置記法で用いる演算子に対して、infixl, infixr, infix などのキーワードを使って、優先順位と結合性を定めることができる。たとえば、Prelude（Haskellにはじめから読み込まれる標準ライブラリ）では次のように宣言されている。

1
2
3
4

infixr 9
infixl 9
infixr 8
infixl 7.
!!
ˆ, ˆˆ, ***, /, ‘quot‘, ‘rem‘, ‘div‘, ‘mod‘, :%, %II - 16

5
6
7
8
9
10
11
12
13

infixl 6
infixr 5
infixr 5
infix 4infixr 3
infixr 2
infixl 1
infixr 1
infixr 0+, :++==, /=, <, <=, >=, >, ‘elem‘, ‘notElem‘&&||>>, >>==<<$, $!, ‘seq‘

infixl は、infixr はを表す。ただの infix はどちらでもないこと（非結合—例えば 1 < x < 2 は構文エラー！）を表す。また、2 列目の数字が大きいほど、優先順位が高い。例えば*は +よりも結合力が強い。
Q 2.8.1 次の式の解釈はどうなるか？括弧を挿入して演算順を明示的にせよ。
1.
x ‘rem‘ 3 /= 1
2.
xs !! 9 : ys ++ zs

バッククォートと逆に本来中置記法で使用される演算子を “(” と “)” でくくって、ふつうの前置記法で用いることができる。例えば1+2 を(+) 1 2 と書くことができる。あるいは関数の引数として渡すこともできる。

Q 2.8.2 次の式を通常の中置記法で書け。括弧はできるだけ省略せよ。
1.
(+) ((*) 2 x) 1
2.
(++) xs ((++) ys zs)

2.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)]]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]
II - 17

Prelude> map (1/) [1,2,3][1.0,0.5,0.3333333333333333]

Q 2.9.1 次のセクションをラムダ式で書け。
1.
([1,2]++)
2.
(!!2)

ただし “-” 演算子は、単項演算子の “-” も存在するので、(-2) はセクションにはならない。その代わり subtract という関数（subtract x y = y - x）が存在するので、subtract 2 と書くことができる。

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

1234

pow4 x = let y = x*x in y*y-- head は Prelude に定義済み
myHead ys = let (z:zs) = ys in z-- myHead (x:xs) = x と定義することもできるなどである。このとき y や z や zs はスコープが限られるので、関数の定義の外
では未定義の変数のままである。

Q 2.10.1 次のような関数を let を用いて定義せよ。
1. 27 乗する関数 pow27
2. リストの尾部（頭部を除いた残り）を求める関数 myTail

この例では 4 乗する関数（pow4）を定義しているが、y*y の部分が変数 y の有効範囲（）に属している。実は、さらに “変数の定義” の右辺の部分（この例では、

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

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

II - 18

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, . . . 5
このリストは、次の箱ポインター記法で表される。

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

Q 2.10.2 repeatList [2,5] が [2,5,2,5,2,5,2,5,2,5, . . . ]、repeatList[1,2,3] が [1,2,3,1,2,3,1,2,3, . . . ] という無限リストになるような関数
repeatList :: [a] -> [a] を定義せよ。なお、引数のリストの要素数は任意である。
ヒント: (++) を使用せよ。

問 2.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
5

Ctrl-c で中断する。

II - 19ただし、where による局所的定義は複数のパターンマッチにまたがることはでき
ない

2.11

Haskell の評価戦略

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





β

M1

?? β
??
?

M2

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

M1 ?

??
?
β ?

M2

M′



 β

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

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

square (3 + 4) = (3 + 4) ∗ (3 + 4)
= 7∗7
= 49
つまり、square の引数である (3+4) は計算されないまま、まず square の定義にしたがって式が展開される。そして、本当に必要になって (この場合は*の引数だから必要) はじめて 2+2 が計算される。この方式をナイーブに実行すると、2+2 が二度計算されてしまう。

II - 20

グラフ簡約では、このような計算をグラフの形で表して、3+4 を一度しか計算しないようにしている。

square




4

 

*

−→

+?

?

3

4

*

−→


+?
 ?



−→

49

7

3

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

1
2

from :: Integer -> [Integer]from n = n : from (n+1)
すると 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])のように有限時間で計算できる。例えば take の計算をするために、第 1 引数が 0でないときは、第 2 引数が空リストかそうでないかを知る必要がある。また、最終的に画面に結果を表示するために、(1+1), (1+1+1) などを評価する必要がある。
なお、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][1,4,7,10,13,16,19]

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

1
+)

1

1
1
2

2
1
3

3
2
5

5
3
8

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

ヒント: zipWith を使う。
問 2.11.3 要素に重複のない昇順に並んだ 2 つのリストをマージして、やはり重複なしの昇順のリストを生成する関数 merge を定義せよ。
問 2.11.4 （難）2i · 3 j · 5k（i, j, k は 0 以上の整数）の形で表せる整数のみを重複なしに昇順に並べたリスト hamming を定義せよ。このリストの 699 番目の要素（ただし最初を 0 番目と数えた場合）が 5898240 であることを確認せよ。
ヒント: map と 問 2.11.3 の merge を使う。

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

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]

II - 22

ただし [1..10] は [1,2,3,4,5,6,7,8,9,10] の略記法である。また、↙ は、本
当は改行しない（プリントの幅の都合で改行している）ことを示している。
リストの内包記法は次のような形のものである。

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

Q 2.12.1 次の内容表記の値は何か?
1. [ x*y | x <- [1,2], y <- [3,5,7] ]2. [ (x,y) | x <- [1,4,7], y <- [2,5,8] , x < y ]問 2.12.2 非負の整数 n を受け取り、0 ≤ x ≤ y ≤ n となるすべての x, y の組を生成する関数 foo :: Integer -> [(Integer, Integer)] を内包表記を用いて定義せよ。
ヒント: .. を使う。
問 2.12.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 = (f x) ++ (bind xs f)
翻訳規則は次のとおりである。（下線部に翻訳規則を再帰的に適用していく。）[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]
II - 23ただし、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]
ただし、ちゃんと動作する定義ではあるが、効率的には改善の余地はいくらでもある。
問 2.12.4 次の内包記法を上の翻訳規則を用いて、unit, bind を用いた形にせよ。

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

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

II - 24

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

問 2.12.6 Haskell 以外の言語で、無限リストをシミュレートする方法を考察せよ。
またそれを用いて、素数列を生成せよ。

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

II - 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 2.13.1
1. all odd [1,3,5] の値は何か?
2. all (>1) [2,0,3] の値は何か?

> safe [1,3] 5
True> safe [1,3] 2
False
となる。

II - 26

Q 2.13.2
1. safe [1,4] 2 の値は何か?
2. safe [1,5] 3 の値は何か?

順に、最初の m 列のすべての安全な配置を調べていく、そのために、そのようなすべての配置 (のリスト) を返す queens という関数を定義する。

1
2
3

queens 0
queens m= [[]]= [ 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 つだけ解を求める計算とすべての解を求める計算を別々に記述する必II - 27

要はなく、しかも、1 つだけ解を求めるためには、それに必要なだけの計算しか行なわない
ちなみに queens 8 を計算させると、> 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 個あることがわかる。
問 2.13.3 他の言語で、8 クイーンを実装せよ。可能ならば、後戻りをシミュレー
トして、一つの解、すべての解をおなじプログラムで効率良く求められるようにせよ。

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

1. ソートされた整数のリストのなかで、3 つ並びの数、3 つの同じ数、2 つの同じ数を見つけてリストアップする関数 shuntsu（順子）、kotsu（刻子）、
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 つ、そろった形である。

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

㡰Ꮚ

ᑐᏊ

II - 28㡰Ꮚ้Ꮚ

2.14 さらに詳しく知りたい人のために . . .
文献 [1] は、Haskell に関するもっとも主要な情報源である。文献 [2] は日本語での Haskell の主要な情報源である。文献 [3] は Haskell の仕様書、Haskell を利用する上での基本ドキュメントである。文献 [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 章）
II - 29

[8] 和田 英一 他 「Haskell プログラミング」
http://www.ipsj.or.jp/07editj/promenade/[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

II - 30