Haskell は純関数型言語ですので、計算はすべて、式 (expression)(構文上の用語)を値(value)(計算の 答とみなす抽象的実体)にすることで行われます。すべての値は型 (type)をもちます。(直観的には型は値の集合と考えることができ ます。) 式の例には整数の 5 や文字の 'a' あるいは関数 \x -> x+1 といったアトミックな値が含まれます。また、 リスト [1,2,3] や組 ('b',4) もあります。
式が値を表しているのと同様に、型の表現式( type expression )は型値(あるいは単に型( type ))を表す構文 上の用語です。型の表現式の例には、Integer (多倍長整数型)、 Char (文字型)、Integer ->Integer ( Integer から Integer への関数)といったアトミックな型と、 [Integer] ( Integer の同型リスト)、 (Char,Integer) (文字型と多倍長整数型の組)というような構造を持つ 型が含まれます。
Haskell の値はすべて「第一級の対象」です。すなわち、関数の引数、関数の返
り値、になり得ます。また、データ構造などのなかに入れることもできます。一
方、Haskell の型は「第一級の対象」ではありません。型はある意味では、値に
ついて記述する役割のものです。このように値とその型を結びつけることを
型付け( typing )といいます。上であげた値と型の例では型付けは
以下のようになります。
5 :: Integer
'a' :: Char
inc :: Integer -> Integer
[1,2,3] :: [Integer]
('b',4) :: (Char,Integer)
:: は「の型は」と読むことができます。
Haskell の関数はふつう一連の等式( equation )によって定義さ
れます。例えば、関数 inc はひとつの等式
inc n = n+1
で定義することができます。
等式は宣言( declaration )の一例です。もうひとつ別の種類の
宣言に型シグネチャ宣言( type signature declaration (§4.4.1 ))があります。
これを用いて inc の明示的な型付けを宣言することができます。
inc :: Integer -> Integer
関数の定義については3節でさら
に詳しく述べます。
学術的な目的で式e1が評価されて、あるいは「簡約」されて 別の式あるいは値e2になることを示したいときには、
e1 => e2
という表記を用います。たとえば、
inc (inc 3) => 5
Haskell の静的な型システムは、型と値とのあいだの形式的関係を定義します。 (§4.1.3) この静的 な型システムは Haskell のプログラムが型安全(type safe)であることを保証するものです。すなわち、プログラマが整合性 のとれていない型を使っていないことを保証します。例えば、一般にふたつの文 字を足し合わせることはできません。つまり、'a' + 'b' は適切に型 付けできないということです。このような静的型付けをおこなう言語のおもな利 点はよく知られているとおり、すべての型エラーはコンパイル時に検出されると いうことです。すべてのエラーがこの型システムで検出されるわけではありませ ん。たとえば、 1/0 という式は型付け可能ですが、評価すると実行時 エラーとなります。しかしながら、この型システムはコンパイル時におおくのプ ログラムエラーを見つけ、ユーザがプログラムの正しさを確認するのに役立つう えに、コンパイラがより効率のよいコード(たとえば、実行時の型タグや型テス トの省略)を生成することができます。
この型システムはユーザがあたえた型シグネチャが正しいことを確認します。本当 のところ Haskell の型システムは強力なので、ユーザは型シグネチャをまった く書かなくてもいいくらいです。この場合には型システムが正しい型推論 (type infer)をおこなってくれます。しかし、チェックのために、 incの例でやったように、型シグネチャをおいておくことは、よい考え です。その理由は型シグネチャは最も効率的なドキュメンテーションであり、プ ログラミング上のエラーを光あるなかにひきだすのに役に立つからです。
[読者のみなさんは気づいたでしょうか、特定の型を表わす識別子は大文字では じまっています。たとえば、Integer や Char です。また、 inc のような値を表わす識別子は小文字ではじまっています。これは単 なる習慣ではありません。Haskell の構文規則でそうすることになっているので す。また、先頭の文字だけではなく、そのほかの文字も、大文字か小文字かとい うことは重要で、foo と fOo と fOO はすべて違 う識別子として区別されます。]
Haskell では多相型(polymorphic type)をとりあつかうことが できます。これはすべての型の上で全称修飾された型を表します。多相型の表現 式は本質的には、型の族をあらわすものです。たとえば、 (∀a)[a] はすべての型aに対して、aの リストの型からなる型の族をあらわしています。整数のリスト(たとえば、 [1,2,3])や文字のリスト (['a','b','c'])、あるいは整数の リストのリストもみなこの族のメンバーです。(しかし、[2,'a']は正 しくない例であることに注意してください。その理由は、2と 'a'の両方を含む単一の型は存在しないからです。)
[上のaのような識別子を型変数(type variable)とよ びます。型変数は大文字にはせず、Intのような特定の型と区別します。 さらに、Haskell には全称修飾された型しか限量子修飾された型はありませんの で、全称限量子をあらわすシンボルを明示的に書く必要がありません。それゆえ、 上の例は単に[a]と書きます。いいかえれば、型変数は暗黙に全称修飾 されています。]
リストは関数型言語ではよく使われるデータ構造で、多相性の概念の説明に丁度 いいデータ構造です。Haskellでは[1,2,3]というリストは、 1:2:3:[]というリストの簡略表記です。ここで、[]は空リス ト、:は中置演算子で最初の引数を2つめの引数(リスト)の前に加えま す。:は右結合性をもちますので、このリストを1:2:3:[]と 書くことができます。
リスト上のユーザ定義の関数の例で、リストの要素の数をかぞえる問題を考えて
みましょう。
length :: [a] -> Integer
length [] = 0
length (x:xs) = 1 + length xs
この定義は、これだけで十分説明になります。この等式をこんなふうに読むこと
ができます。「空リストの長さは 0 、最初の要素がxで残りが
xsであるようなリストの長さは 1 にxsの長さを加えたもの
である。」(ここでは命名の習慣がつかわれていることに注意してください。
xsはxの複数形で、読むときもそのように読みます。)
直観的にわかりますが、この例では Haskell の重要な側面が浮き彫りになって います。これはまだ説明していませんが、パターンマッチング (pattern matching)です。定義の等式の左辺には[]や x:xsというパターンが含まれています。関数適用の際に、これらのパ ターンは直観でわかるとおりに実引数にマッチします([]は空リストに のみマッチし、x:xsは少なくとも1つ以上の要素をもつリストにマッチ します。このとき、xは最初の要素に束縛され、xsはリスト ののこりの部分に束縛されます)。マッチングが成功すると、右辺が評価され、 それが関数適用の結果として返されます。もし、マッチングが失敗すれば、次の 等式が試されます。すべての等式でパターンマッチが失敗すれば、エラーとなり ます。
パターンマッチを使って関数を定義するのは Haskell では常套手段です。ユー ザは Haskell で許されている種々のパターンについて慣れておく必要がありま す。パターンマッチについては 4節でもう一度とりあげます。
関数lengthは多相関数の1例でもあります。この関数はあらゆる型の要 素をもつリストに適用することができます。たとえば、[Integer]、 [Char]あるいは[[Integer]]です。
length [1,2,3] | => | 3 |
length ['a','b','c'] | => | 3 |
length [[1],[2],[3]] | => | 3 |
もう2つ別のよく使うリスト上の多相関数をあげておきましょう。関数
headはリストの最初の要素を返し、関数tailは最初の要素を
のぞく残りの部分を返します。
head :: [a] -> a
head (x:xs) = x
tail :: [a] -> [a]
tail (x:xs) = xs
関数lengthとは違い、これらの関数はその引数のすべての値に対して
定義されているわけではありません。これらの関数が空リストにたいして適用さ
れた場合には実行時エラーが起こります。
多相型を使うと、或る種の型が厳密には別の型よりも一般的な(定義されている値 の集合がより大きい)ことに気付きます。たとえば、型[a]は型 [Char]よりも一般的であるということです。いいかえれば、後者の型 は、適切な置換をほどこせば、前者の型から後者の型を導出できるということで す。この一般性の順序付けに関していえば、Haskell の型システムは2つの重要 な特性を発揮します。ひとつめは、正しく型付けされた式はいづれも唯一の主型 (これについては下で説明します)を持つことが保証されるということです。ふた つめはこの主型は自動的に推論できるものであるということです(§4.1.3)。Cのように単 態型を用いる言語と比較すると、多相性のある言語では表現力がアップしている のがわかると思います。型推論機構は、プログラマが型の問題で頭を悩ますこと を軽減してくれます。
式あるいは関数の主型は直観的には「その式のすべてインスタンスを含む」最も 一般性のない型ということができます。たとえばheadの主型は [a]->aで、[b]->aやa->aあるいは aでは一般的すぎます。かといって、[Integer]->Integer というのでは限定的すぎます。唯一の主型が存在するというのは、 Hindley-Milner型システムのhallmarkな特徴です。この Hindley-Milner型システムは、Haskell や ML そして Miranda (Miranda は Research Software Ltd.の登録商標)あるいはその他の言語(ほとんどは関数型言 語)の型システムの基盤となっています。
Haskellではdata宣言を使って、ユーザ自身が型を定義することができ ます。例をあげていきましょう(§4.2.1)。
Haskellの定義済の型でもっとも重要な型は、真理値の型です。
data Bool = False | True
ここで定義した型はBool型です。この型はちょうど2つの値
TrueとFalseを持っています。型Boolは(無引数)
型構築子(type constructor)の例です。また、True
やFalseは(これも無引数)データ構築子(data
constructor)(単に構築子ともいう)の例です。
同じようにして、色の型を定義しましょう。
data Color = Red | Green | Blue | Indigo | Violet
Bool型とColor型はともに列挙型の例です。それは、どちら
も有限個の無引数データ構築子から構成されているからです。
つぎにあげるのは、ひとつのデータ構築子のみからなる型の例です。
data Point a = Pt a a
単一の構築子から構成されているので、Pointのような型はしばしばタ
プル型(tuple type)と呼ばれます。これは、本質的にはべつの型の
直積(この場合は2引数)だからです。(タプル型は別の言語ではレコード型と呼ば
れているものに類似しています。) 一方、BoolやColorのよ
うな複数の構築子をもつ型は直和型((disjoint) union or
sum type)と呼ばれます。
しかし、重要なことはPointは多相型の例だということです。すべての 型 t に対して、これは t を座標の型とする点を定義するものです。 Point型はあきらかに1引数の型構築子です。それは、型 t から新しい 型Point t が生みだされているからです。(同様に先にでてきたリスト の例でいうと[]も型構築子です。与えられたすべての型にたいして、 []を「適用」することができて、それが新しい型 [t]となります。Haskell の構文では[t] を[] t と書くことも許されています。同じように -> は型構築子です。与えられた 2 つの型 t と u に対して、 t->u は型 t の要素から型 u の要素への写像をおこなう関数の型 です。)
2引数データ構築子Ptの型は
a -> a -> Point aであることに注
意してください。つまり次のは正しい型付けです。
Pt 2.0 3.0 :: Point Float
Pt 'a' 'b' :: Point Char
Pt True False :: Point Bool
一方、Pt 'a' 1のような式は正しく型付けできません。そ
れは、'a'と1は別の型だからです。
データ構築子を適用して値を得ることと、型構築子 を適用して型を得ることを区別することが重要です。前者は、実行時 に起こりHaskellのなかでどのように計算するかということであり、後者はコン パイル時に起こり、型安全を確かめる型システムのプロセスの一部です。
[Pointのような型構築子とPtのようなデータ構築子は別の名
前空間にあります。つまり、つぎのように、型構築子とデータ構築子に同じ名前
を使うことができるということです。
data Point a = Point a a
最初はちょっとややこしく見えるかもしれないですが、これで型とデータ構築子
の関連が明らかなものになります。]
型は再帰的に構成することもできます。たとえば、二分木の型を考えてみましょ
う。
data Tree a = Leaf a | Branch (Tree a) (Tree a)
ここでは多相型の二分木を定義しました。その要素はa型の値を含む「葉」
のノードかあるいは(再帰的に)ふたつのサブツリーを含む「枝」のノードです。
このようなデータ宣言をよむ場合には、Treeは型構築子であり、
Branch や Leaf はデータ構築子であることを思いだしてく
ださい。これらの構築子間の関係を理解したら、上の宣言は本質的には以下のよ
うなBranchの型やLeafの型の定義であることがわかるでしょ
う。
Branch :: Tree a -> Tree a -> Tree a
Leaf :: a -> Tree a
この例で表現力の豊かな型を定義したので、いくつかの興味深い(再帰)関数を定
義することができます。たとえば、fringeという、木を左から右へ
たどって「葉」にある要素のリストを返す関数を定義したいとしよう。このよう
な場合、最初に新しい関数の型を最初に書きおろしておくとあとで役にたつこと
が多いです。この場合関数の型はTree a -> [a]で
なければならないことがわかります。すなわちfringeは多相関数で、
全て型 aについて、aの木をaのリストへ写像しま
す。その定義は次のようになります。
fringe :: Tree a -> [a]
fringe (Leaf x) = [x]
fringe (Branch left right) = fringe left ++ fringe right
ここで、++は中置演算子で、2つのリストを連結します。(この演算子
の完全な定義は9.1 節で与え
ます。). まえにあげた length の例と同じように、fringe
関数は、パターンマッチを使って定義します。ちがいは、ここではユーザ定義の
構築子 Leaf と Branch があることです。[仮引数は小文字
ではじまっているので、すぐにわかることに注目してください。]
利便性をため、Haskellでは、型の同義名(type
synonym)を定義する方法があります。すなわち、よく使う型に名前をつける
というものです。型の同義名は型宣言によって作り出します(§4.2.2)。例をあげましょう。
type String = [Char]
type Person = (Name,Address)
type Name = String
data Address = None | Addr String
型の同義名は新しい型を定義するわけではなく、単に、既存の型に新しい名前を
与えるものです。たとえば、Person -> Name という型
は (String,Address) -> String と全くおなじものです。
型の同義名の新しい名前は、ふつう元の型より短いものになりますが、短い名前
をつけることだけが型の同義名の目的ではありません。型の同義名をニーモニッ
クとするこで、プログラムの可読性が改善されます。上はまさにその例です。多
相型にも新しい名前を付けることができます。
type AssocList a b = [(a,b)]
これは、型aの値と型bの値を結びつける「連想リスト
(association list)」という型です。
これまで、リスト、タプル、整数、文字など、いくつかの「組み込み」型を紹介 しました。また、あたらしいユーザ定義の型の定義の方法も示しました。構文が 特別である以外に、組み込みの型は、ユーザ定義の型にくらべて特別なことはあ るのでしょうか?答えはノーです。特別な構文は利便性と歴史的な慣 習のためのもので、意味としてはなにも違いがありません。
この点をさらに強調するために、組み込みの型の宣言がどのようなものになりう
るかを考えてみましょう。もし、型の宣言の構文を組み込みの型に使えるとした
ら、たとえば、Char型はこんな風に書けるでしょう。
data Char = 'a' | 'b' | 'c' | ... -- This is not valid
| 'A' | 'B' | 'C' | ... -- Haskell code!
| '1' | '2' | '3' | ...
...
これらの構築子名は実際には正しいものではありません。この点は次のようにし
なければならないでしょう。
data Char = Ca | Cb | Cc | ...
| CA | CB | CC | ...
| C1 | C2 | C3 | ...
...
これらの構築子は簡単なものですが、文字を表わすにはかなり不便なものです。
いずれにせよ、このような「擬似Haskell」のコードを書くことで、特別な構文 の見通しがつけやすくなります。これで、Char型が数多くの無引数構 築子から構成されている列挙型であることがわかります。 Char についてこのように考えていくと、たとえば、なぜ関数の定義の なかで文字に対してパターンマッチを使うことが可能なのかが理解できると思い ます。つまり、あらゆる型の(データ)構築子にたいしてパターンマッチを使えそ うだということがわかります。
[この例では、Haskell におけるコメントの使いかたも示しています。 --とそれに続く行末までのすべての文字は無視されます。Haskellでは さらに入れ子になったコメントも可能です。それは、 {-...-} という形式のものでコード中のどこにでも置くこと ができます(§2.2)。]
同様に考えれば、Int (固定精度の整数)やIntegerの定義は
data Int = -65532 | ... | -1 | 0 | 1 | ... | 65532 -- more pseudo-code
data Integer = ... -2 | -1 | 0 | 1 | 2 ...
のように考えることができます。ここで、-65532と65532は、
いわば、与えられた処理系における固定精度整数の最小値と最大値です。
IntはCharに比べればはるかに大きな列挙型ですが、それで
も、有限の列挙型です。一方、Integerに対する擬似コードでは無
限の列挙型を表現しようとしています。
タプルもこのやりかたで簡単に定義できます。
data (a,b) = (a,b) -- more pseudo-code
data (a,b,c) = (a,b,c)
data (a,b,c,d) = (a,b,c,d)
. .
. .
. .
上の各宣言はそれぞれ、特定の長さの一つのタプルを定義しています。
(...)は(データ構築子として)式の構文中と(型構築子として)型の表現式の構
文中にあらわれます。最後の宣言の後の縦につづく点はこのような宣言の無限の
列をあらわしています。これは、Haskellではあらゆる長さのタプルが許されて
いることを反映しています。
リストも同様に簡単に定義できます。リストの場合は再帰的になっているのが面
白いですね。
data [a] = [] | a : [a] -- more pseudo-code
以前にリストについて述べたことが、これで明解になります。[]は空
リストであり、:はリストの中置構築子です。つまり、
[1,2,3]は1:2:3:[]と同等であるはずです。(:は右
結合性をもちます。) [] の型は [a] で、 : の型
は a->[a]->[a] です。
[ここでの「:」の定義方法は構文的に正しい方法です。中置構築子を data宣言中で使用することが許されています。また、中置構築子と中 置演算子は区別されます。(中置構築子はパターンマッチの処理で使用します。) 中置演算子の定義では、「:」が先頭にこなければならないことからも、中置構 築子と中置演算子が区別されていることがわかります。]
ここでは、タプルとリストの違いを注意深くみておく必要があります。上の定義 でその違いがハッキリわかります。注目すべき点は、リストの型は同じ型の要素 上の任意の長さの再帰的構造を持ち、一方、(特定の)タプルの型は別の型の要素 上の固定の長さの非再帰構造であることです。タプルとリストの型付けルールは もう明かでしょう。
(e1,e2,...,en), n>=2 に対して、もし、 ti が ei の型であるとす るならば、タプルの型は (t1,t2,...,tn) です。 [e1,e2,...,en], n>=0 に対して各 ei が必ず同じ型 t であるなら、そのリストの 型は [t] です。
Lisp 系の言語でもそうであるように、リストというのは Haskell でもややこし
いものです。それで、他の関数型言語と同様に、Haskell にはリストを生成する
ための糖衣構文があります。いま議論したばかりのリストの構築子の他に、
Haskell ではリストの内包表記(list comprehension)として知
られる表現が使えるようになっています。次の例がよい解説になります。
[ f x | x <- xs ]
この式は直観的に、「xs から順に引き出してきた x について
f x をすべて集めたリスト」("the list of all f x
such that x is drawn from xs")と読むことができます。
集合のときの表記との類似性は偶然ではありません。
x <- xs の部分は生成部(generator)
とよばれています。生成部を複数持つこともできます。
[ (x,y) | x <- xs, y <- ys ]
このリスト内包表記は、xs と ys の2つのリストの直積とな
ります。要素は生成部が左から右へ「入れ子」になっているかのように選ばれて
いきます。(もっとも右にある生成部がもっとも速く変化します。) ですから、
xs を [1,2] とし、ys を [3,4] とすれ
ば、その結果は [(1,3),(1,4),(2,3),(2,4)]となります。
生成部のほかに、ガード(guard)とよばれているブール式を書
くことができます。ガードは生成される要素に制約を与えます。例として、みな
さんお馴染のソーティングアルゴリズムの定義をあげておきます。
quicksort [] = []
quicksort (x:xs) = quicksort [y | y <- xs, y<x ]
++ [x]
++ quicksort [y | y <- xs, y>=x]
さらに Haskell はリストの数列表記という構文もサポートしています。 これも例でみていくのがいいでしょう。
[1..10] | => | [1,2,3,4,5,6,7,8,9,10] |
[1,3..10] | => | [1,3,5,7,9] |
[1,3..] | => | [1,3,5,7,9, ...(infinite sequence) |
数列表記について詳しくは 8.2 節で、「無限リスト」につ いては 3.4 節で解説します。
組み込みの型の糖衣構文をもうひとつあげておきましょう。文字列リテラルの
"hello" は実際には文字のリスト ['h','e','l','l','o']
の簡略表記です。実際、"hello" の型は String で、これは
定義の型の同義名になっています。
type String = [Char]
ということは、定義済のリスト上の多相関数は文字列に対しても適用できるとい
うことです。たとえば、
"hello" ++ " world" => "hello world"