やさしい Haskell 入門 ( バージョン 98 )
back
next
top
このセクションでは、Haskell の定義済標準型クラスを紹介しましょう。これら のクラスは、あまり関心のないメソッドについては省略したかたちで、すでに簡 単に紹介しました。Haskell レポートにはより完全な解説があります。一部のク ラスについては Haskell の標準ライブラリの一部になっています。これらのク ラスについては Haskell ライブラリレポートに記述されています。
Eq クラスと Ord クラスについては既に議論しています。
プレリュードにある Ord クラスの定義は、以前に定義した単純なもの
よりも、いささか複雑です。特に、compare メソッドは、以下のよう
になっています。
data Ordering = EQ | LT | GT
compare :: Ord a => a -> a -> Ordering
compare メソッドがあれば、このクラスの他のすべてのメソッドは(デ
フォルトメソッドで)定義できます。 Ord のインスタンスを生成する
にはこの方法が一番すぐれています。
Enum クラスには数列表現の糖衣構文の底流にある一連の演算がありま す。たとえば、数列式 [1,3..] は enumFromThen 1 3 を表わしています。(形式的な変換につ いては §3.10 を参照してください。) これで、Enum のインスタンスの型であればど の型に対しても、この数列式を用いてリストの生成ができることがわかります。 Enum のインスタンスにはほとんどの数値型が含まれているばかりでは なく、Char 型も含まれており、['a'..'z'] はアルファベッ ト順にならべた、小文字のリストを表わします。さらに、Color のよ うな、ユーザ定義の列挙型を Enum のインスタンスとして宣言できま す。それは次のようになります。
[Red .. Violet] => [Red, Green, Blue, Indigo, Violet]
ここで、注意すべきことは、このような列は、算術的であるということです。す なわち、各値の増分はそれが数値であろうとなかろうと、一定であるということ です。Enum のほとんどのインスタンスは固定長の整数上に写像するこ とが可能です。この目的のために、fromEnum や toEnum が 用意されており、Int と Enum のインスタンスの間での変換 をおこないます。
Show クラスのインスタンスは文字列への変換(典型的目的は I/O )が
可能な型です。Read クラスには、その値を表現する文字列を構文解析
する演算が用意されています。Show クラスの最も単純な関数は
show です。
show :: (Show a) => a -> String
show は当然、対応する型のあらゆる値をとり、その表現として、文字
列(文字のリスト)を返します。たとえば、show (2+2) は
"4" を返します。このように正しく動作するものについてはいいので
すが、それぞれの型のいろいろな値について、もっと、複雑な表現が必要になり
ます。たとえば、
"The sum of " ++ show x ++ " and " ++ show y ++ " is " ++ show (x+y) ++ "."
のような場合、それぞれの文字列を連結しているのでは、能率的ではありません。
ことに、 2.2.1 節での二分
木の文字列表現を考えてみましょう。入れ子になった部分木を表示するために適
当なマークをつけてたり、左の枝と右の枝をわける印をつけたりします。
showTree :: (Show a) => Tree a -> String
showTree (Leaf x) = show x
showTree (Branch l r) = "<" ++ showTree l ++ "|" ++ showTree r ++ ">"
(++) は左側の引数の長さの線型で効く計算量をもちますので、
showTree は木のサイズの 2 次で効く計算量になります。
線型の複雑さを持つように、関数 shows を以下のように定義します。
shows :: (Show a) => a -> String -> String
この shows は印字可能な値と文字列をとり、前の部分にその値の文字
列表現を連結した文字列を返します。ふたつめの引数は一種の文字列積算子
になります。show は shows にナル積算子をあたえたものと
して定義することができます。これは Show クラスの定義のなかの
show のデフォルトの定義となります。
show x = shows x ""
shows を使って、showTree のより効率のよい定義をするこ
とができます。このときも、文字列積算子引数をもたせます。
showsTree :: (Show a) => Tree a -> String -> String
showsTree (Leaf x) s = shows x s
showsTree (Branch l r) s= '<' : showsTree l ('|' : showsTree r ('>' : s))
この定義により効率の問題は解決しました。( showsTree の計算量は
線型のオーダです。) しかし、この関数の表現をさらに改良することができます。
まず、型シノニムをつくってみましょう。
type ShowS = String -> String
この型は、なにかの文字列表現に積算子文字列を連ねた文字列を返す関数の型で
す。つぎに、積算子をもちまわり、長い文字列の構築の右端での括弧の蓄積を
回避するために、関数合成を使うことができます。
showsTree :: (Show a) => Tree a -> ShowS
showsTree (Leaf x) = shows x
showsTree (Branch l r) = ('<':) . showsTree l . ('|':) . showsTree r . ('>':)
コードを整理することよりもさらに重要なことが、このプログラム変換によって
あきらかになりました。それは、オブジェクトレベルでの表現から
関数レベルの表現への変換です。ここで、showsTree の型付
けは、tree から 表示関数 への写像ということができます。
('<' :) あるいは ("a string" ++) の
ような関数はプリミティブな表示関数で、関数合成を用いて、より複雑な関数を
構築することができます。
さて、tree を文字列に換えるはなしに戻りましょう。こんどは逆の問題を考えま
す。基本のアイディアは、型 a に対する構文解析子です。型
a の構文解析子は文字列を引数としてとり、
(a, String) のリストを返す関数です[9]。プレリュー
ドにはこのような関数の型シノニムが備えられています。
type ReadS a = String -> [(a,String)]
ふつうの状況では、パーザは単一の要素を含むリストを返します。この要素は、
入力文字列から読み込んだ型 a の値と、そのあと構文解析される、残
りの文字列の組です。もし、構文解析が不可能であれば、結果は空リストです。
もし、2 つ以上の構文解析が可能であるなら(この場合は曖昧な構文ということ
になります)、結果は、2 つ以上の組を含むリストになります。標準関数の
reads は Read のあらゆるインスタンスに対応する構文解析
子関数です。
reads :: (Read a) => ReadS a
この関数を使って、showTree を使ってつくった、二分木の文字列表現
を構文解析する関数を定義することができます。リストの内包表記はこのような
構文解析関数を構築するのに便利なイディオムです。(モナドや構文解析結合子
を使ったもっとエレガントな方法もあります。これらは、ほとんどの Haskell
システムとともに配布される標準の構文解析ライブラリの一部となっています。)
readsTree :: (Read a) => ReadS (Tree a)
readsTree ('<':s) = [(Branch l r, u) | (l, '|':t) <- readsTree s,
(r, '>':u) <- readsTree t ]
readsTree s = [(Leaf x, t) | (x,t) <- reads s]
すこし、時間をかけてこの関数の定義を詳細にみていきましょう。考慮すべき状
況がふたつあります。もし、構文解析の対象となる文字列の最初の文字が
'<' の場合、これは、枝の表現にちがいありません。そうでなかっ
た場合、これは葉の表現です。最初の場合は、開き三角括弧につづく入力文字列
の残りの部分を s とすると、可能な構文解析はなんであれ、
Branch l r となり、残りの文字列は、u となり、
以下の条件に従います。
上の 2 つめの定義等式は葉の表現に対する構文解析は、この木の要素の表現を 構文解析し、その結果に構築子 Leaf を適用して、値をうる、という 意味です。
信仰上、とりあえず、(色々な型があるなかで) Integer の Read (および Show) インスタンスがあって、期待通りの振 舞いをする reads が備わっていることを受容しましょう。つまりは以 下のとおりです。
(reads "5 golden rings") :: [(Integer,String)] => [(5, " golden rings")]
これが理解できれば、次の評価を確認できるはずです。
readsTree "<1|<2|3>>" | => | [(Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3)), "")] |
readsTree "<1|2" | => | [] |
いま定義した readsTree には、2 つの欠点があります。
ひとつは、この構文解析器はたいへん厳格にできていて、木の表現の文字列の要
素の前や間に空白を許さないというもので、もうひとつは、区切の記号を構文解
析する方法が葉の値の場合と部分木の場合ではすっかり違うということです。こ
の統一性のなさが、この関数の定義を読みづらいものにしています。この 2 つ
の問題をプレリュードで定義されている字句解析器を使って解決することができ
ます。
lex :: ReadS String
lex は通常は、文字列の組の単一要素のリストを返します。その組は、
入力の最初の字句と入力ののこりです。ここでの字句のルールは、Haskell
プログラムの字句のルールです。lex は空白をスキップします。もし、
入力文字列が空あるいは空白およびコメントしか含まなければ、lex
は [("","")] を返します。もし、この意味で空ではなく、かつ、空白
のつづく有効な字句ではじまっていない場合には、lex は
[] を返します。
この字句解析器を使うと、木の構文解析器はこんなふうになります。
readsTree :: (Read a) => ReadS (Tree a)
readsTree s = [(Branch l r, x) | ("<", t) <- lex s,
(l, u) <- readsTree t,
("|", v) <- lex u,
(r, w) <- readsTree v,
(">", x) <- lex w ]
++
[(Leaf x, t) | (x, t) <- reads s ]
さて、ここで、readsTree と showsTree を使って、
Read のインスタンス
(Read a) => Tree a と Show
のインスタンス (Show a) => Tree a を宣言
してみましょう。こうすれば、木の構文解析と表示用にプレリュードにある総称
的多重定義関数を利用することができます。さらに、構成要素に木を含むほかの
多くの型の構文解析や表示ができるようになります。たとえば、
[Tree Integer] のようなものです。ここでわかるように、
readsTree と showsTree はほぼ、Show および
Read のメソッドの型を満しています。showsPrec と
readsPrec のメソッドは、shows と reads をパラ
メータ化したものです。追加されたパラメータは、優先レベルです。これは、中
置構築子が式に含まれている場合に正しく、括弧付けをおこなうために使用しま
す。Tree のような型に対しては優先度は無視されます。
Show と Read のインスタンスとしての Tree は以
下のようになります。
instance Show a => Show (Tree a) where
showsPrec _ x = showsTree x
instance Real a => Read (Tree a) where
readsPrec _ s = readsTree s
また、Show のインスタンスは showTree を使って、次のよ
うに定義することもできます。
instance Show a => Show (Tree a) where
show t = showTree t
しかし、これは、ShowS バージョンよりも効率の面で劣ります。
Show クラスでは showsPrec と show の両方につ
いてデフォルトのメソッドを定義しており、ユーザはインスタンスひとつにつき、
どちらかを定義すればいいようになっています。これらのデフォルトメソッドは
相互再帰的になっていますので、インスタンス宣言のなかで、これらの関数のど
ちらも定義しなかった場合、呼び出しの際にループを引き起こします。
Num のようなクラスの場合でも、このような「相互ロック性のデフォ
ルトメソッド」があります。
Read および Show クラスの詳細に興味のあるむきは、レポー トの §D を参 照してください。
(read . show) (これは恒等関数になるはず)をいくつかの
木に適用することで Read および Show のインスタンスをテ
ストすることができます。ここで、read は reads を特殊化
したものです。
read :: (Read a) => String -> a
入力に対して、構文解析結果が唯一でない場合、あるいは、入力が、
a の型のひとつの値に対して 2 つ以上の表現(あるいは、コメントや
空白)を含むような場合には、この関数は失敗します。
5 節で紹介した木の
Eq インスタンスについて思いだしてください。このような宣言をいち
いち書くのは単純ですが、面倒です。葉の要素の型が同値型であることを要求し
ているのですから、2 つの葉は同値の要素をもつ場合、そして、その場合にかぎ
り同値であり、ふたつの枝は、その左の部分木と右の部分木がそれぞれ等しい場
合、かつ、その場合にかぎり等しいわけで、それ以外の場合、ふたつの木は同値
ではありません。
instance (Eq a) => Eq (Tree a) where
(Leaf x) == (Leaf y) = x == y
(Branch l r) == (Branch l' r') = l == l' && r == r'
_ == _ = False
幸い、この面倒な作業を、新しい型の同値演算子が必要になるたびに繰り返す必
要はありません。Eq インスタンスは、データ宣言でそのように指定す
れば、自動的に導出されます。
data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving Eq
deriving 節は暗黙のうちに、
5 節にあるように Eq
インスタンス宣言を生成します。Ord、Enum、Ix、
Read、Show の各インスタンスも同様に deriving
節を使って生成することができます。
[ここでは 2 つ以上のクラス名を指定することができます。その場合にはクラス
の名前リストは括弧でかこまれ、名前はそれぞれコンマで区切る必要があります。]
Tree に対して導出された Ord インスタンスは Eq
の場合にくらべていくぶん複雑です。
instance (Ord a) => Ord (Tree a) where
(Leaf _) <= (Branch _) = True
(Leaf x) <= (Leaf y) = x <= y
(Branch _) <= (Leaf _) = False
(Branch l r) <= (Branch l' r') = l == l' && r <= r' || l <= l'
ここでは、辞書順 を指定しています。構築子は、data 宣言
中でその出現の順にならべられています。そして、構築子への引数は左から右へ
と比較されていきます。組み込みのリスト型は意味論的には2つの構築子をもつ
型と同じであることを思いだしてください。実際にこの完全な定義は
data [a] = [] | a : [a] deriving (Eq, Ord) -- pseudo-code
です。(リストは、Text インスタンスでもありますが、これは導出さ
れません。) リストに対して導出された Eq および Ord の
インスタンスはごくふつうのものです。特に、文字のリストとしての文字列は、
その基になる Char 型の順序によって、ならべられます。先頭部分文
字列はそれより長い文字列よりも小さいと判定します。たとえば、
"cat" < "catalog" です。
実際問題として、Eq および Ord のインスタンスは、ほとん どの場合、ユーザの定義ではなく、導出されます。 実際、すこしばかり、どきどきしますが、同値関係と全順序関係という代数的 な性質を維持するように注意しながら、独自の同値述語や順序述語を定義しなけ ればなりません。 自動詞的な (==) 述語は、たとえば、大変苦痛で、プログラムを読 むものを困惑させ、手動あるいは自動的な、(==) 述語が明白な同値性 の近似であることに依存する、プログラム変換を困難なものにします。 とはいうものの、導出されるものとはちがう Eq あるいは Ord のインスタンスが必要な場合もあります。もっとも重要な例は、 同じ抽象値をあらわす別の具体的な値となるような抽象型のインスタンスの例で す。
列挙型は導出された Enum のインスタンスをもちます。ここで、この
型の順序は data 宣言での構築子の出現順になります。たとえば、
data Day = Sunday | Monday | Tuesday | Wednesday
| Thursday | Friday | Saturday deriving (Enum)
このとき、この型に対して導出されたインスタンスを用いた単純な例は次のよう
なものになります。
[Wednesday .. Friday] | => | [Wednesday, Thursday, Friday] |
[Monday, Wednesday ..] | => | [Monday, Wednesday, Friday] |
その構成要素が Read (Show) のインスタンスであるような 型なら、その型に対して Read (Show) のインスタンスであ ることを導出することが可能です。(標準の型のほとんどについては、 Read および Show のインスタンスであることが、プレリュー ドのなかで示されています。 関数の型である (->) のような型の いくつかは、Show インスタンスではありますが、それに対応した Read のインスタンスではありません。) 導出された Show インスタンスで定義されるテキストでの表現は、対象となる型の Haskell での 定数式の見かけと整合性があります。例えば、型 Day について Show と Read をその deriving 節に加えると、
show [Monday .. Wednesday] => "[Monday,Tuesday,Wednesday]"
を得ることができます。