tnomuraのブログ

Data.List unfoldr

Haskell の Data.List モジュールにはリストを処理する数多くの関数が定義されている。リスト関連の関数は、畳込み以外の関数は直感的にもわかりやすい。foldr などの畳み込み関数はわかりにくかったが、それも、畳み込みが行われる様子をトレースするとわかるようになる。たとえば foldr (*) 1 [1,2,3,4,5] の計算は次のようなカッコのなかに展開される計算だ。展開後、右端から計算が進んでいくので foldr すなわち、右からの折りたたみと言うのだろうと思う。

foldr (*) [1,2,3,4,5] = (1 * (2 * (3 * (4 * (5 * 0)))))

また、この計算は次のような再帰関数と同じなので、一種の無名再帰関数として使うこともできる。

product [] = 0

product (x:xs) = x * (product xs)

ところが、unfoldr だけは未だに理解できないでいた。Data.List の Hackage では foldr の双対で foldr が リストから値を計算するのに対し、unfoldr は値の seed からリストを生成すると簡単に説明されているが何のことかわからなかった。関数の型を調べても次のようになり意味がわからない。

Prelude> import Data.List
Prelude Data.List> :t unfoldr
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

b -> Maybe (a, b) 型の関数と b 型の引数をとり、[a] 型のリストを返すとなっているが、第１引数の関数の戻り値がなぜ、Maybe 型なのか、どうして seed のデータ型が b で戻り値のデータ型が a 型のリストなのか理解し難い感じがしていた。

こういうときは実例を試してみるのが一番だ。まずは、b 型のデータも、a 型のデータも同じ整数にしてみた。実験したら無限リストが生成されてしまったので take 関数で切り取った。

Prelude Data.List> take 10 $ unfoldr (\x -> Just (x,x)) 1
[1,1,1,1,1,1,1,1,1,1]

b -> Maybe (a, b) 型の関数が \x -> Just (x, x) で得られる値が [a] 型のリストだから、この関数だと 第２引数に与えた 1 が無限に繰り返すリストを生成するのだろう。このままでは、あまりおもしろくないので戻り値の Just (x, x) のペアの第２要素を関数で加工するようにしてみた。

Prelude Data.List> take 10 $ unfoldr (\x -> Just (x, x+1)) 1
[1,2,3,4,5,6,7,8,9,10]

どうも Maybe (a, b) の b の方は再帰関数の再帰部分 recursive case を書くと良いようだ。b の部分には b 型の値と言うより b 型の値を戻す b -> b 型の関数を書くのが良いようだ。そこで x + 1 を x * 2 に変えてみた。

Prelude Data.List> take 10 $ unfoldr (\x -> Just (x, x*2)) 1
[1,2,4,8,16,32,64,128,256,512]

次に不思議だったのが、b -> Maybe (a, b) のペアの第１要素の方がなぜ a なのかということだ。なぜ、a と b と言うように seed の値と unfoldr が戻すリストの値 [a] の型をわざわざ変えているのだろうか。だが、上の例から、これは a 型の値ではなく b -> a 型の関数を使うのではないだろうかと思いついた。x * 2 という再帰的定義で b に与えられた seed の値が変化していくが、それを引数にして a 型のデータを生成するのではないかということだ。そこで Just (x, x*2) のペアの第１要素を [x] に変えてみた。

Prelude Data.List> take 10 $ unfoldr (\x -> Just ([x], x*2)) 1
[[1],[2],[4],[8],[16],[32],[64],[128],[256],[512]]

思ったとおりだ。b -> Maybe (a, b) の意味はペアの b に b -> b 型の関数を与えると次々に値を変更していくが、ペアの a に b -> a 型の関数を与えると、生成された b 型の値を引数に a 型の値を生成させることができる。

最後の疑問はなんで b -> Maybe (a, b) の関数の値が Maybe 型なのかということだが、上の仕組みがわかってきたので、これは再帰関数の停止条件を Nothing が帰ってくることで判別しているのではないかと思いついた。b -> Maybe (a, b) 型の関数で戻り値が Just (a, b) のときは値の生成が行われるが、Nothing が返るとその動作が終了してしまうのだ。そこで実験してみた。

Prelude Data.List> unfoldr (\x -> if x > 600 then Nothing else Just ([x], x*2)) 1
[[1],[2],[4],[8],[16],[32],[64],[128],[256],[512]]

今度は停止条件があるので、take 関数を使わないで済んだ。まだ、なぜ unfoldr が foldr の双対なのかという疑問は残るが、unfoldr でとにかくリストが生成できることがわかったので満足だ。

関数の型からその動作を推測する際に、型変数が単純なデータだと考えては間違えることがこの例でわかる。

Prelude Data.List> :t unfoldr
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

b -> Maybe (a, b) の ペアの a, b が単なる値ではなくそれぞれ b -> a という関数、 b -> b という関数であると気づいたときに unfoldr の意味がわかったからだ。このあたりの事情は関数の型シグネチャーからは読み取ることが難しい。そこが unfoldr の動作を読み解くことができなかった一番の理由だ。

Hakell を学んでいて引っかかるのは、抽象的な関数に出会ったときだ。しかし、関数を読み解くときの障害になるこの抽象性が、プログラムを書くときに驚くほど簡潔でそれ自身が意図を語るような表現になる最大の要因なのだ。

また、Haskell のこの抽象性は数学者が一般人にはわからない高級な概念を操作しているというものではなく、様々なプログラムで発生する共通のパターンを簡潔に表現できるという意味の抽象性だ。関数型言語が実用的かどうかは議論があるだろうが、関数型言語を学ぶことで、プログラムの本質的なパターンを発見することに敏感になることはできる。

箱入りデータと fmap, <$> , <*>

Haskell には箱入りデータがある。例えばリストは [] という箱の中にデータが入っているし、Maybe型は Just a という箱の中に、Either型は Right a, や Left b という箱の中にそれぞれ生のデータが入っている。しかし、このような箱入りのデータには直接には関数適用できない。たとえば、(*2) を箱入りデータの Just 2 に直接適用することはできない。

Prelude> (*2) (Jutst 2)

<interactive>:15:7: error:
• Data constructor not in scope: Jutst :: Integer -> a
• Perhaps you meant ‘Just’ (imported from Prelude)

このように、箱入りデータは、関数の直接的な適用から保護されている。しかし、データが一旦箱入りデータになってしまったらなんの操作もできないというのは不便だ。そこで、Prelude ではこのような箱入りデータを加工する方法がいくつか提供されている。

たとえば、map 関数はこのような箱入りデータに作用する関数の代表的なものだ。これは、第１引数の関数を、第２引数のリストという箱入りデータに関数適用することを可能にしてくれる。

Prelude> map (*2) [1,2,3]
[2,4,6]

しかし、残念ながら map はリスト以外の箱入りデータに作用できない。例えば Maybe 型のデータに map を適用することはできない。

Prelude> map (*2) (Just 2)

<interactive>:17:11: error:
• Couldn't match expected type ‘[b]’
with actual type ‘Maybe Integer’
• In the second argument of ‘map’, namely ‘(Just 2)’
In the expression: map (* 2) (Just 2)
In an equation for ‘it’: it = map (* 2) (Just 2)
• Relevant bindings include it :: [b] (bound at <interactive>:17:1)

そこで、fmap の登場だ。fmap は Functor クラスのインスタンスのデータに対し map と同じような作用を起こすことができる。fmap は リストの箱入りデータと同じように、map 関数を、Maybe型や、Either型のデータに関数適用することを可能にしてくれる。

Prelude> fmap (*2) (Just 2)
Just 4
Prelude> fmap (*2) (Right 2)
Right 4

fmap はリスト型のデータにも適用できるがその動作は map 関数と同じものになる。

Prelude> fmap (*2) [1,2,3]
[2,4,6]

このように、プログラマーからの立場としては、fmap 関数は map 関数の拡張として捉えることができる。

同様に <$> 演算子も map の拡張と考えていい。これは、Applicative クラスの関数だが、Prelude 上でプログラムするときは、その厳密な意味を知る必要はない。単に <$> もまた map 関数の拡張と考えても動作させることができる。実際 <$> をリストに適用すると次のようになる。

Prelude> (*2) <$> [1,2,3]

[2,4,6]

fmap と同じように <$> 演算子は左項の関数を、右項の箱入りデータに関数適用することができる。

Prelude> (*2) <$> (Just 2)
Just 4
Prelude> (*2) <$> (Right 2)
Right 4

<$> のすごいところはそれだけではない、<$> のあとに <*> を続けることによって２変数関数を箱入りデータに関数適用できるのだ。

Prelude> (+) <$> [1,2,3] <*> [1]
[2,3,4]
Prelude> (+) <$> Just 2 <*> Just 3
Just 5
Prelude> (+) <$> Right 2 <*> Right 3
Right 5

この <$> と <*> 演算子は Applicative タイプクラスの関数だ。

<$> と <*> の本当の意味は上に述べた説明とは少々異なっているが、さしあたって上の例の使い方を知っているだけで、Functor クラスや Applicative クラスというような用語が出たときに、途方にくれる必要がなくなる。要するにこれらは map の拡張なんだという（誤った）理解であってもその使い方のイメージを持っているだけで随分気分が楽になる。

Haskell の特徴だが、理論的には難しくても使ってみるとなんとなくわかる。Functor や Appkicative という用語の意味がわからなくても、fmap や <$> や <*> を使ったプログラム例を試しているだけで、そのようなプログラムが現れたときに拒否反応を起こさないですむ。

再帰関数の作り方 順列

Haskellで順列のプログラムを自分で作ってみた。まず関数の名前を perm とし、関数の型を決めた。

perm :: [a] -> [[a]]

perm はリストを引数にとり、リストのリストを値として戻す。例えば、

perm [1,2,3] = [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

のようになることを期待している。ここで [1, 2, 3] から perm [1, 2, 3] を手作業で作ることを考えてみる。まずリストの要素 1 を取り出すと、残りは [2, 3] というリストになる。[2, 3] の順列は perm [2,3] で次のようになる。

perm [2, 3] = [[2,3], [3,2]]

そこで prem [2,3] の順列の先頭に 1 を置くとperm [1,2,3] の順列のうち先頭の要素が 1 である順列 [1,2,3], [1, 3, 2] ができる。これは Haskell で次のように計算できる。

Prelude> map (1:) [[2,3], [3,2]]
[[1,2,3],[1,3,2]]

また、これは perm を使って次のように記述できることを示している。

map (1:) (perm [2,3])

perm [2,3] のリスト [2,3] は (filter (/=1) [1,2,3]) で計算できるので上の式は、つぎのように書ける。

map (1:) (perm (filter (/=1)) [1,2,3])

さらに、1 を変数 x に置き換えると、上の式は次のようになる。

map (x:) (perm (filter (/=x) [1,2,3]))

この式がきちんと働くかどうかを確かめたいが、perm がどのような関数かはまだわからないので、テスト用に perm [2,3] = [[2,3], [3,2]] を定義しておく。実験した結果が次のようになった。

Prelude> let perm [2,3] = [[2,3], [3,2]]
Prelude> (\x -> map (x:) (perm (filter (/=x) [1,2,3]))) 1
[[1,2,3],[1,3,2]]

そこで閃いた。[1,2,3] から 1, 2, 3 をそれぞれ取り除いたリスト [2,3], [1,3], [1,2] の perm の値を予め定義しておいたら、perm [1,2,3] を計算する再帰式をテストできるのではないかということだ。そこでやってみた。

Prelude> :{
Prelude| perm [2,3] = [[2,3],[3,2]]
Prelude| perm [1,3] = [[1,3],[3,1]]
Prelude| perm [1,2] = [[1,2],[2,1]]
Prelude| :}

Prelude> (\x -> map (x:) (perm (filter (/=x) [1,2,3]))) 1
[[1,2,3],[1,3,2]]
Prelude> (\x -> map (x:) (perm (filter (/=x) [1,2,3]))) 2
[[2,1,3],[2,3,1]]
Prelude> (\x -> map (x:) (perm (filter (/=x) [1,2,3]))) 3
[[3,1,2],[3,2,1]]

これは、それぞれ、リスト [1,2,3] から 1 を取り出して先頭においた場合の順列、2 を取り出して先頭においた場合の順列、３を取り出して先頭においた場合の順列を出力している。map を使うとこれらを一気に実行できる。

Prelude> map (\x -> map (x:) (perm (filter (/=x) [1,2,3]))) [1,2,3]
[[[1,2,3],[1,3,2]],[[2,1,3],[2,3,1]],[[3,1,2],[3,2,1]]]

いい感じだが出力がリストのリストのリストになっているのでリストのフラットなリストにしたい。そこで、先頭の map をconcatMap に変えてみた。

Prelude> concatMap (\x -> map (x:) (perm (filter (/=x) [1,2,3]))) [1,2,3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

いい感じだ。これは次の式が成立していることを示している。

perm [1,2,3] = concatMap (\x -> map (x:) (perm (filter (/=x) [1,2,3]) [1,2,3]

そこでこれを一般化して perm の再帰部分 recursive case を定義してみた。

perm xs = concatMap (\x -> map (x:) (perm (filter (/=x) xs))) xs

これが働くと仮定して、prem xs の境界条件 base case を考えてみる。リスト [1] について上の定義が成立している場合、

prem [1] = concatMap (\x -> map (x:) (perm [])) [1]

となるが、perm [1] = [[1]] となるためには perm [] = [[]] でなければならない。これで、perm の再帰部分と境界条件が定義できたので、次のように perm を定義してみた。

Prelude> :{
Prelude| perm [] = [[]]
Prelude| perm xs = concatMap (\x -> map (x:) (perm (filter (/=x) xs))) xs
Prelude| :}

この定義は次のようにうまく動く。

Prelude> perm [1,2,3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

再帰関数の再帰部分 recursive case の定義がうまく動くかどうかのテストは、関数の定義にその関数自身が現れるのでなかなか難しいが、このように小規模な事例を工夫してテストすることで動作を確認しながら定義していくことができる。

エラトステネスのふるい

素数を見つけるのにエラトステネスのふるいという方法がある。２から始まる自然数を並べておいて、２を残して２で割り切れる数を全て消していくと、[2, 3, 5, 7, 9, ... ] となる。さらに、３を残して3で割り切れる数を消していくと、[2, 3, 5, 7, 11, 13, ..] となる。これを無限に繰り返していけば素数を列挙して見つけることができる。これを Haskell でやってみる。

まずは、２を除いた数列 [3, 4, 5, 6, 7, 8, .. ] から２で割り切れない数を集めたリストを作る。

Prelude> filter (\y -> mod y 2 /= 0) [3..10]
[3,5,7,9]

これを改良して、リストの先頭の数を取り出し、残りのリストからその数で割り切れない数のリストを作る sieve_one 関数を作ってみる。

Prelude> sieve_one (x:xs) = filter (\y -> mod y x /= 0) xs
Prelude> sieve_one [2..10]
[3,5,7,9]

このリストを先程の先頭の要素のあとに追加する sieve_append 関数を作ってみる。

Prelude> sieve_append (x:xs) = x : filter (\y -> mod y x /= 0) xs
Prelude> sieve_append [2..10]
[2,3,5,7,9]

なんとなくやり方がわかってきたのでこの操作を (2, (3, (4, ... ))) と続けていくような再帰的定義ができないかを考えてみる。

Prelude> sieve (x:xs) = x : sieve (filter (\y -> mod y x /= 0) xs)

この定義だと、

sieve [2, 3, 4, .. ] =

2 : sieve [3,5,7, ..] =

2 : 3 : sieve [5, 7, .. ] = ...

と次々に展開されるように思われる。そこで [2..10] に sieve を関数適用してみる。

Prelude> sieve [2..10]
[2,3,5,7*** Exception: <interactive>:40:1-57: Non-exhaustive patterns in function sieve

途中経過は良さそうだがエラーが出てしまった。再帰関数の終了条件が定義されていないと指摘されている。そこで、sieve を [2..] という無限リストに適用して、take 10 で先頭の１０個の素数だけを取り出した。Haskell のこのアバウトな感じが大好きだ。

Prelude> take 10 $ sieve [2..]
[2,3,5,7,11,13,17,19,23,29]

再帰的定義 recursive case だけを定義して、それを無限リストに適用するというテクニックは使い勝手がよさそうだ。

再帰関数の作り方

リストの要素から n 個とる組み合わせを全て列挙するプログラムを例にとって、再帰関数の作り方を考えてみた。

再帰関数を作るときにまず考えるのは、その関数の名前と型だ。再帰関数を作るときは、その関数がまず定義済みだと仮定して考えていくのが便利だからだ。そこでこの関数の名前を comb とすることにするとその型シグネチャーは次のようになる。

comb :: n -> [a] -> [[a]]

つまり、関数 comb は元のリストから取り出す要素の個数とその要素を取り出す元となるリストを引数にとり、組み合わせのリストのリストを戻り地とすることになる。

つぎにやることは、comb の定義の再帰部分 recursive case を考えることだ。これは、comb がすでに定義されていると考えると、定義がしやすくなる。recursive case を定義するために、実際の例でテストをしてみる。[1, 2, 3] というリストから2つの要素を取り出す組み合わせのリストを作ることを考えてみよう。すなわち、comb 2 [1, 2, 3] の再帰部分を考えてみる。

まず、[1, 2, 3] から先頭の要素の 1 を取り出すと 1 と残りの要素 [2, 3] にわけられる。目的の組み合わせのひとつは、この 1 と残りの [2, 3] のうちの一つからなる組み合わせ [[2], [3]] を合わせて [[1, 2], [2, 3]] を作ることだ。しかし、これだけでは十分ではない。組み合わせにはこのほかに、残りのリスト [2, 3] から2つ取る組み合わせ [[2, 3]] も含まれるからだ。したがって、目的の組み合わせは次のような式で表せる。

map (1:) [[2], [3]] ++ [[2, 3]]

これは実際に ghci で計算することができる。

Prelude> map (1:) [[2],[3]] ++ [[2,3]]
[[1,2],[1,3],[2,3]]

上の計算を comb を使って記述してみよう。

comb 2 [1, 2, 3] = map (1:) (comb 1 [2, 3]) ++ comb 2 [2, 3]

これを、次のように一般化すると comb の再帰部分 recursive case が完成する。

comb n (x:xs) = map (x:) (comb (n-1) xs) ++ comb n xs

さらに、この漸化式を使って comb の境界条件 base case を定義する。まず、リスト [1, 2, 3] から1個だけをとりだす組み合わせを考えると、

comb 1 [1, 2, 3] = map (1:) (comb 0 [2,3]) ++ comb 1 [2, 3]

これは [[1], [2], [3]] になるはずだから、

map (1:) (comb 0 [2,3]) ++ comb 1 [2, 3] = [[1], [2], [3]]

である。この式で左辺の comb 0 [2, 3] がどのような値になるのかを考える。comb 1 [2, 3] は [[2], [3]] だから、

map (1:) (comb 0 [2, 3]) = [[1]]

でなければならない。したがって、

comb 0 [2, 3] = [[]]

であることがわかる。comb 0 [2, 3] = [] だと、map (1:) (comb 0 [2, 3]) = [] となって要素の 1 が消し飛んでしまうからだ。このへんの事情は第2引数の [2, 3] がどのようなリストであっても同じである。したがって、次の定義が境界条件 base case の一つとなる。

comb 0 _ = [[]]

さらに、comb n xs の境界条件はもう一つ必要だ。comb のもう一つの引数 xs についての境界条件も必要だからだ。そこで xs = [] となるような場合を考えてみる。これは [1] から1つの要素を取り出す場合、すなわち、comb 1 [1] を考えるとよい。すなわち、

comb 1 [1] = map (1:) (comb 0 []) ++ comb 1 []

である。comb 0 [] = [[]] であるから map (1:) (comb 0 []) = map (1:) [[]] = [1] である。あきらかに comb 1 [1] = [1] だから、

comb 1 [] = []

でなくてはならない。comb 1 [] = [[]] でも良さそうだがそれだと、

comb 1 [1] = [[1], []]

となって、余計な [] が戻り値に混ざってしまう。したがって、 comb 1 [] = [] でなければならない。それでは comb 2 [] の場合などうだろうか。

comb 2 [] = map (:) (comb 1 []) ++ comb 1 []

となっておかしなことになるので、comb 2 [] = [] としなければならない。したがって、一般化して初期条件の2つ目が決まる。すなわち、

comb _ [] = []

である。境界条件を決めることができたので、あらためて comb のプログラムを作ってみてテストしたらうまく動くようだ。

Prelude> :{
Prelude| comb 0 _ = [[]]
Prelude| comb _ [] = []
Prelude| comb n (x:xs) = map (x:) (comb (n-1) xs) ++ comb n xs
Prelude| :}
Prelude> comb 3 [1..4]
[[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

このように、再帰関数を定義するときは再帰部分 recursive case を定義するより境界条件 base case を求めるほうが難しい。しかし、再帰関数の引数がどのような場合にも再帰部分の等式が成り立つように考えていくことで、境界条件を求めることができるのだ。

再帰関数の定義は、右辺に自分自身の関数が現れるのでイメージしにくいが、その関数がすでに定義済みであると仮定して、再帰部分、境界部分の順に定義していけばそれぼど難しいものではない。

再帰関数と畳込み

プログラムを記述するときにループは必須だ。同じ種類の操作を繰り返すプログラムはアプリケーションを作るときに必須だからだ。手続き型の言語には、while, do ~ until, for ~ in など数種のループの記述法があるが、Haskell でループを記述する方法は再帰関数を定義するという方法があるだけだ。

ところが、この再帰関数というのがわかりにくい。たとえば、再帰関数で必ず例示される階乗の関数だが、次のように、fact n を定義するのに、それ自身の関数 fact (n-1) を使っている。まだ定義もされていない関数でそれ自身を定義するのだからおかしな話だが、下の例のようにきちんと動いてしまう。

Prelude> :{
Prelude| fact 0 = 1
Prelude| fact n = n * fact (n-1)
Prelude| :}
Prelude> fact 5
120

納得できないので、上のプログラムをその計算の過程が見えるように、「見える化」をしてみた。

Prelude> :{
Prelude| fact 0 = "1"
Prelude| fact n = "(" ++ (show n) ++ "*" ++ fact (n-1) ++ ")"
Prelude| :}
Prelude> fact 5
"(5*(4*(3*(2*(1*1)))))"

これなら、計算の過程がわかるので納得できる。つまり、こういう手順で計算されているのだ。fact 5 を計算するのに、まず 、5* という計算をひとまずスタックか何かに保存しておく、すると fact n の定義から 5 * fact 4 となるから、fact 4 を計算する。これも定義から確定した値が得られるわけではないので 4* という計算を保存しておく。つまり (5 * (4 * fact 3)) となるわけだ。このように fact を次々に展開していくと最後に fact 0 が残るが。これは確定値の 1 だここでやっと計算を実行することができる。すなわち、

(5*(4*(3*(2*(1*1)))))

が計算され、結果が120になる。このように左辺を定義するのに同じ名前の関数を使っているが、引数の値が次々に減少していくために、次々に置き換えていけば最終的に base case の fact 0 = 1 にたどり着いて、無事計算できるというわけだ。

ところで、上の計算は畳み込み関数の foldr 関数の計算に似ている。foldr の計算を「見える化」したのが次のプログラムだ。

Prelude> foldr (\x y -> "(" ++ x ++ "*" ++ y ++ ")") "1" ["5","4","3","2","1"]
"(5*(4*(3*(2*(1*1)))))"

つまり、畳み込み関数は、再帰関数の一種なのだ。また、foldr を使えば再帰関数に名前をつける必要がないので、無名再帰関数として利用することができる。

このように、再帰関数は数式を次々に展開していくことで値を計算する方法だと理解すると、なんとなく納得できる。

再帰関数について補足すると、クイックソートのように式の展開が一方向ではなく左右両方向に行われる場合も、式が次々に展開されていくという事情は同じだ。

Prelude> :{
Prelude| qsort [] = []
Prelude| qsort (x:xs) = "[" ++ qsort (filter (<=x) xs) ++ "[" ++ x ++ "]" ++ qsort (filter (>x) xs) ++ "]"
Prelude| :}
Prelude> qsort ["2", "0", "1", "8"]
"[[[0][[1]]][2][[8]]]"

これはリストの先頭の要素 [2] を中心にそれ以下の要素と、それ以上の要素に分け、

[0, 1] ++ [2] ++ [8]

その両端のリストについてもその操作を次々に適用していくことがわかる。

Haskell のループは再帰関数のみなので、再帰関数が理解できれば、繰り返しのあるプログラムを書くのに抵抗がなくなる。

do 記法を使わない IO プログラム

"Haskell 2010 Language Report" に do 記法を使わない IO モナドのプログラムの例が載っていたので今はそのようなプログラムの書き方もするのだろうかと思って真似してみた。ターミナルから文字列を入力してそれをそのまま表示するプログラムだ。空文字列（リターンキーのみ）を入力するとプログラムが終了する。

Prelude> :{
Prelude| main =
Prelude|   getLine >>= \x ->
Prelude|   if x == ""
Prelude|     then
Prelude|       return ()
Prelude|     else
Prelude|       putStrLn x >>
Prelude|       main
Prelude| :}
Prelude> main
hello
hello
world
world

Prelude>

do 記法の時と同じように手続き型風のプログラムが書ける。ちょっと煩雑な気もするが、糖衣構文ではないので、エラーの箇所も端的にわかる。これからは、このような記述法も普及していくのだろうか。

do 記法とは何か

IO モナドで苦労するのは、do 記法でプログラムを書いたとき訳の分からないエラーが発生するからだ。それは、一つには do 記法が一体何なのかをコンパイラレベルで知らないからだ。コンパイラレベルでは一体 do 記法はどのように扱われているのだろうかと疑問に思って調べてみたら、"Haskell 2010 Language Report" に簡潔に説明されていた。Haskell 2010の3.14 は Do Expression となっている。

Do 記法はコンパイラ的には 「式」だったのだ。以下はその引用だ。do 式の文法が記述されている。

3.14 Do Expressions

lexp	→	do { stmts }	(do expression)
stmts	→	stmt1 … stmtn exp [;]	(n ≥ 0)
stmt	→	exp ;
	|	pat <- exp ;
	|	let decls ;
	|	;	(empty statement)

A do expression provides a more conventional syntax for monadic programming. It allows an expression such as

putStr "x: " >>
getLine >>= \l ->
return (words l)

to be written in a more traditional way as:

do putStr "x: "
l <- getLine
return (words l)

手続き型風のプログラムから、関数型のプログラムへの変換法も記述してある。

Translation:Do expressions satisfy these identities, which may be used as a translation into the kernel, after eliminatingempty stmts:

do {e}	=	e
do {e;stmts}	=	e >> do {stmts}
do {p <- e; stmts}	=	let ok p = do {stmts}
		ok _ = fail "..."
		in e >>= ok
do {let decls; stmts}	=	let decls in do {stmts}

The ellipsis "..." stands for a compiler-generated error message, passed to fail, preferably giving someindication of the location of the pattern-match failure; the functions >>, >>=, and fail are operations in theclass Monad, as defined in the Prelude; and ok is a fresh identifier.

As indicated by the translation of do, variables bound by let have fully polymorphic types while those defined by<- are lambda bound and are thus monomorphic.

上の記事の表を見ながらいろいろな do 記法を試してみた。

Prelude> do {putStrLn "hello"; putStrLn "world"}
hello
world
Prelude> putStrLn "hello" >> putStrLn "world"
hello
world

Prelude> do {c <- getLine; putStrLn c}
hello
hello
Prelude> getLine >>= \c -> putStrLn c
hello
hello

Prelude> do {let {h = "hello, "; w = "world"}; putStrLn (h ++ w)}
hello, world
Prelude> let {h = "hello, "; w = "world"} in putStrLn (h ++ w)
hello, world

これで、どういうプログラムを作れば do 記法でエラーが出ないのかが何となくわかる気がしてきた。たとえば、do 記法の最後は必ず(モナド）式でないといけないことが分かる。IOモナドの垣根がこれで一気に低くなるかもしれない。

do 記法

前回の記事で述べたようにHaskell の IO モナドは 1 引数で戻り値が IO モナド型の関数を >>= で連結したものだ。IOモナド型関数を「モナド式」と呼ぶらしいのでこの用語を使うと、IOモナドを利用した入出力関数は次のようになる。

モナド式 >>= モナド式 >>= ... >>= モナド式

これは手続き型言語のプログラムとは相当異なっている。しかし、この IO モナドのプログラムを見かけ上手続き型のプログラムと同じように見せるために do 構文を使ったシンタックスシュガーがある。「モナド・ウォークスルルー - Haskell」によると、do 構文は次のような形をしている。

do {式１; 式2； ... ; 式n}

この 式 i には Haskell の式なら何でもよいというわけではなく次の3つの場合に制限される。

(a) モナド式　(引数が一つで戻り値が IO a 型の関数）

(b) パターン <- モナド式

(c) let {宣言 1 ; 宣言 2 ; ... ; 宣言 n }

do 構文はブロックなかの式の並びを上に述べた、モナド式 >>= モナド式 >>= ... というモナド式の連結に変換する働きがあると考えてよい。たとえば次の do 構文を使った手続き言語風のプログラムは、

Prelude> :{
Prelude| do
Prelude| c <- getLine
Prelude| putStrLn c
Prelude| :}
hello, world
hello, world

次のようなモナド式を >>= 演算子で連結したプログラムに変換することができる。

Prelude> getLine >>= \c -> putStrLn c
hello, world
hello, world

また、変数が2つ以上ある場合も

Prelude> :{
Prelude| do
Prelude| x <- getLine
Prelude| y <- getLine
Prelude| putStrLn (x ++ y)
Prelude| :}
hello,
world
hello, world

次のようにモナド式と >>= 演算子だけのプログラムに変換できる。

Prelude> getLine >>= \x -> (getLine >>= \y -> putStrLn (x ++ y))
hello,
world
hello, world

このように、モナド式と >>= 演算子だけのプログラムに変換できないようなプログラムが、手続き言語の類推で書かれていた場合、意味不明のエラーメッセージに悩むことになる。そういうエラーは、IOモナドの本質をつかんでいればたやすく発見できるが、手続き言語の類推では発見できない。

IO モナドに挑戦するのは、Haskell に十分慣れてからでもいい。ghci 上で作業をしていれば、IO モナドがなくてもかなりの処理ができるからだ。

IOモナドを理解するのに圏論はいらない

Haskellを学ぶ人が必ず引っかかるのは IO モナドだろう。管理人も IO モナドを理解したくて圏論の教科書を読んだりした。しかし、結論から言うと、圏論のモナドは理解できなかったし、IO モナドを活用するのに圏論は全く必要なかった。

端的に言うと、IO モナドとは、引数が１個で戻り地が IO a 型の関数を >>= 演算子で数珠つなぎに結合したものだ。IO モナドを活用しようと思ったら、そういう関数を作って >>= 演算子で繋いでやれば全く問題なく動作する。たとえば、次のプログラムは IO モナドのプログラムだ。

Prelude> getLine >>= putStrLn
hello, world
hello, world

getLine と putStrLn の型を調べると次のようになる。

Prelude> :t getLine
getLine :: IO String
Prelude> :t putStrLn
putStrLn :: String -> IO ()

getLine は端末から String を取得して IO String を返す関数だし、putStrLn は String を引数にとり IO () を返す関数だ。どちらも引数一つをとり、IO a 型の値を返す関数なのだ。

したがって、自分の IO プログラムを作ろうと思ったらそのような関数を定義すればいい。例えば、文字列を引数にとりその文字列に "hello" をつける関数を作ってみよう。

Prelude> let hello name = return ("hello, " ++ name)
Prelude> hello "Dolly"
"hello, Dolly"

return という関数は IO モナドのプログラムを書くときに必須の関数で、引数を IO a 型のデータにラッピングして戻り値とする働きがある。値を返す IO モナドのプログラムを書くためには、必ずこの return 関数で IO a 型にラッピングして返さなければならない。

この関数を先程の getLine >>= putStrLn の間に挟むとコンソールから入力した文字列に "hello, " をつけて出力できる。

Prelude> getLine >>= hello >>= putStrLn
Dolly
hello, Dolly

こうしてみると、演算子 >>= の役割がわかる。それは IO a 型にラッピングしたデータを受け取って、そのなかのデータ a を取り出して次の関数に渡す働きをしているのだ。IO モナドとは、１引数 IO a 型戻り値の関数、これを IO モナド型関数と呼ぶことにすると、IO モナド型関数 >>= IOモナド型関数 >>= ... >>= IO モナド型関数のように、ひたすら IO モナド型関数を演算子 >>= でつないだもので、IO モナドについて語るべきなのはこれで全てだ。

do 記法とは、このような IO モナド型の関数を見かけ上手続き型のプログラムに見えるようにするためのシンタックスシュガーでしかない。do 記法で理解不能なエラーが出る場合は、自分の書いたプログラムが IO モナド型の関数だったのかどうかを考えることでその原因を突き止めることができる。

Haskell で入出力プログラムを書く必要がない場合は、IO モナドを学ぶ必要はない。ghci の扱い方に習熟すれば、大抵のプログラムを Haskell で書いてテストしてみることができる。入出力関係のプログラムを学習するのはある程度 Haskell に慣れたあとでやったほうがいい。

K & R で最初に現れるプログラムは "hello, world" だが、Haskell では適当ではない。Haskell で最初に習うべきなのは map 関数ではないのだろうか。

Prelude> map (*2) [1..5]
[2,4,6,8,10]

このプログラムを、１から５までのリストに要素をそれぞれ２倍にするという操作を適用するプログラムだと説明すると、その効果に驚いて Haskell をやってみたいと思うようになるのではないだろうか。