Haskell とモナド

今日までに理解した Haskell とモナドについて、まとめてみます。間違っているところもあると思いますので、コメントを期待しています。(_ _)

Haskell の特徴

純粋関数型言語です。

参照透過性

変数は初期化できますが、一旦決まった値は変更できません。関数の返す結果は、引数の値だけで決まります。

遅延評価

データの処理は、本当にデータが必要になったときに実行されます。UNIX のパイプみたいなものだと考えるといいでしょう。

Haskell にも副作用はあります。

よい Lisper は、副作用のある関数とない関数を分けて実装します。しかし、そうでない Lisper が分けてくれるとは限りません。

Haskell を使うと、副作用のある部分とない部分を必然的に分けて書くことになります。

変数の値は変更できない

たとえば、有名な quicksort を例にとりましょう。

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

命令型言語の発想では、元々のリストの中身が置き換えられるのだと思ってしまいます。しかし、次々と新しいリストが生成されているのです。

このように、命令型で代入したいと思うところでは、新しいデータを作るという発想の転換が必要です。

ループ

変数の値が書き換えられないので、インデックスを使う for 文はありません。ループは、再帰で実現します。

fib 1 = 1
fib 2 = 1
fib n = fib (n - 1) + fib (n - 2)
fib 6 → 8

また、リストのすべての要素を操作したいと思うのであれば、写像関数(map)を利用します。

plus1 n = n + 1
map plus1 [1, 2, 3] → [2, 3, 4]

遅延評価

遅延評価では、実行順序が決まらないので、IO 出力の順番も決まらないことになります。Haskell の説明には、こういう文章が散見しますが、実際に順番が決まらない例は示されていません。

そこで山下さんに、順番が決まらない例を教えて頂きました。

以下の例では、予想通りの順番で出力されます。なお、sequence_ は、(モナドの)リストを取り、要素を順に実行して、値は返さない関数です。

sequence_ [ putStr "foo", putStr "bar" ] → "foobar" と表示

以下の例では、直感的にはまずリストが評価されるので、ここで "foobar" と出力され、そのあとにリストが逆転されるように見えます。

sequence_ (reverse [ putStr "foo", putStr "bar" ]) → "barfoo" と表示

しかし、表示されるのは "barfoo" です。これは　reverse する際に、リストの要素を評価する必要がないからです。リストの要素は、sequence_ が使うときにはじめて評価されます。つまり、これは以下のように書くのと同じになります。

sequence_ [ putStr "bar", putStr "foo" ] → "barfoo" と表示

モナドとは何か？

純粋関数型言語では、以下のことが問題になります。

• (たとえば for 文の break のような)制御構造をどう実現するか？
• (遅延評価にわずらわされずに)実行順序を指定するにはどうするか？

これらを解決する仕組みがモナドです。

モナドとは、具体的には「あるデータに付ける付加情報」です。ラベルとかタグだと思ってもいいでしょう。モナドでは、代入文などは再導入されませんから、純粋関数型言語の世界を壊すことはありません。

モナドでは、2つの関数を定義する必要があります。

return

あるデータにラベルを付けてモナドを生成して返す関数です。

>>=

bind と読みます。左側のモナドから中身を取り出し、右側の関数を適応させる演算子です。結果は、新しいモナドになります。

return

代入できないということは、現在割り当てられているメモリの内容を書き換えられないということです。逆に言えば、メモリを新たに割り当てて付加情報としても問題ないでしょう。関数でこれが許される部分は、戻り値です。ですから、この関数の名前は return といいます。

たとえば、Maybe モナドを使う場合、文字列 "foo" に return を適応すると、Just "foo" のようにラベルが付きます。

-- Maybe の文脈で
return "foo" → Just "foo"

モナドによっては、ラベルを剥がして中身を取り出せます。Maybe モナドの中身を取り出す関数は、fromJust です。

module Maybe
fromJust(return "foo") → "foo"

>>=

bind は、左を実行してから右を実行します。(bind の一般的な性質なのか、Maybe/IO モナドの bind だけの性質なのか分っていません。) このおかげで、実行順序が決まります。

モナド >>= f → 新しいモナド

左から右へ行くことが分るように、このような記号になっているのでしょう。

3つのモナド則の内 1 つが、この性質を表しています。

(return x) >>= f == f x

Maybe モナド

プログラミング言語一般で、以下のような条件式を考えてみて下さい。

a == "foo" && b == "bar" && c == "baz"

どこかで false になれば、それ以降を評価せずに、全体が false になります。これは、一種の制御構造です。false になったら break されると考えていいでしょう。

この制御構造では、値そのものが制御に使われています。値と制御情報を分けるにはどうすればいいでしょうか？

Maybe モナドを使うと、値を保持しながら、ラベルによって制御を実現します。別の言い方をすると、Maybe モナドは、失敗するかもしれない演算を連結するために使います。

Monad の定義は、以下のようになっています。

data Maybe a = Nothing | Just a

instance Monad Maybe where
    return         = Just
    fail           = Nothing
    Nothing  >>= f = Nothing
    (Just x) >>= f = f x

ラベルは、Just か Nothing です。Just が true、Nothing が false だと思っていいでしょう。>>= は && に相当します。

Maybe モナドの一般的な使用例としては、データベースの検索が挙げられます。データベースを検索し、データがあれば、さらにそれに対して別の検索、なければ終了という制御を実現できます。

db = [("alice", [("title", "Ms."), ("job", "sales")]),
          ("bob",   [("title", "Mr."), ("job", "engineer")])]
return db >>= lookup "bob" >>= lookup "job"
→ Just "engineer"

たとえば "chris" で検索すると、途中で演算が終了し Nothing が返ります。

return db >>= lookup "chris" >>= lookup "job"
→ Nothing

return と >>= を強調するためにこういう風に書きましたが、以下のように書いても構いません。

lookup "bob" db >>= lookup "job"

あるいは命令型言語風にも書けます。

do person <- lookup "bob" db
   lookup "job" person

「"<-" がモナドの中身を取り出す」、「次の行に行くのが右の関数を適応する」ことに相当すると考えていいでしょう。

IOモナド

入出力には IO というラベルが付きます。

たとえば、putStr という文字列出力関数は以下のように使います。

putStr "Hello, World"

return との関連を考えるために、わざわざ return を使ってみるとこうなります。

return "Hello, World" >>= putStr

>>

同じ種類のモナドは、">>" で連結できます。

putStr は1つの IO モナドを返しますから、putStr 同士を ">>" で連結できます。

return "Hello, " >>= putStr >> return "World!" >>= putStr >> return "" >>= putStrLn

">>" の左と右とでは、データのやりとりはありません。左が先に評価され、次に右が評価されます。このため、出力の順番を指定できます。

return があると見にくいので、書き換えてみましょう。

putStr "Hello, " >> putStr "World!" >> putStrLn ""

これも do を使って命令型風に書き直すことができます。

do putStr "Hello, "
   putStr "World!"
   putStrLn ""

ある関数の型に IO が現れない場合、その関数の中で putStr などを使うことはできません。デバッグのための表示コードを追加することも許されないのです。これによって、純粋関数型言語の世界を守ります。