「ほっ」と。キャンペーン

<   2013年 03月 ( 23 )   > この月の画像一覧

Haskell ワンライナー ghci 版

以前の記事の「Haskell ワンライナー」の実行例が Hugs 版で見づらかったので ghci 版で記述してみた。ghci でマルチラインを使うためには、:set +m コマンドでマルチライン対応にしておく。マルチラインを解消するには :unset +m と入力する。

Prelude> :set +m

定番の階乗の計算(再帰関数)

Prelude> let
Prelude| fact 0 = 1
Prelude| fact n = n * fact (n-1)
Prelude|
Prelude> fact 5
120

フィボナッチ数(無限数列)

Prelude> let fib = 0:1:zipWith (+) fib (tail fib)
Prelude|
Prelude> take 10 fib
[0,1,1,2,3,5,8,13,21,34]

素数(内包的定義)

Prelude> let sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x /= 0]
Prelude|
Prelude> take 10 $ sieve [2..]
[2,3,5,7,11,13,17,19,23,29]

順列( concat の使用例)

Prelude> :m Data.List
Prelude Data.List> let
Prelude Data.List| perm [] = [[]]
Prelude Data.List| perm xs = concat [map (x:) $ perm (delete x xs)| x <- xs]
Prelude Data.List|
Prelude Data.List> perm "abc"
["abc","acb","bac","bca","cab","cba"]

組み合わせ(引数が2つの場合の再帰関数)

Prelude Data.List> let
Prelude Data.List| comb _ 0 = [[]]
Prelude Data.List| comb [] _ = []
Prelude Data.List| comb (x:xs) n = map (x:) (comb xs (n-1)) ++ comb xs n
Prelude Data.List|
Prelude Data.List> comb "abcd" 2
["ab","ac","ad","bc","bd","cd"]

配列の長さ(ワイルドカード _ の使い方)

Prelude Data.List> let
Prelude Data.List| mylength [] = 0
Prelude Data.List| mylength (_:xs) = 1 + mylength xs
Prelude Data.List|
Prelude Data.List> mylength [1,2,3]
3

クイックソート(左右の再帰)

Prelude Data.List> let
Prelude Data.List| qsort [] = []
Prelude Data.List| qsort (x:xs) = qsort (filter (<x) xs) ++ [x] ++ qsort (filter (>= x) xs)
Prelude Data.List|
Prelude Data.List> qsort "world"
"dlorw"

要素の挿入( let 〜 in 構文の使い方)

Prelude Data.List> let
Prelude Data.List| insertAt x xs n =
Prelude Data.List|   let (ys,zs) = splitAt n xs
Prelude Data.List|   in ys ++ [x] ++ zs
Prelude Data.List|
Prelude Data.List> insertAt 'X' "abcd" 2
"abXcd"

Maybe モナド(モナドのプログラム)

Prelude Data.List> let double x = 2 * x
Prelude Data.List|
Prelude Data.List> Just 2 >>= return . double
Just 4

IOモナド(入出力の基本)

Prelude Data.List> do
Prelude Data.List|   cs <- getLine
Prelude Data.List|   putStrLn cs
Prelude Data.List|
hello, world
hello, world

ファイルの書き込み( writeFile 関数の使い方)

Prelude Data.List> writeFile "test.txt" "hello, world"

ファイルの読み込み( readFile 関数の使い方)

Prelude Data.List> readFile "test.txt" >>= putStrLn
hello, world

データのシリアライズ( show 関数の使い方)

Prelude Data.List> writeFile "array.txt" (show [1,2,3])
Prelude Data.List> readFile "array.txt" >>= putStrLn
[1,2,3]

データの読み出し( read 関数の使い方)

Prelude Data.List> readFile "array.txt" >>= print . sum . (read :: String -> [Int])
6
[PR]
by tnomura9 | 2013-03-31 16:45 | Haskell | Comments(0)

北朝鮮の臨戦態勢

北朝鮮が一方的に臨戦態勢を宣言して、ニュースから目が離せないが、どうしてこのような暴挙に出たのか興味がある。

金正恩書記がアメリカのバスケットボール選手に対して託した電話会談をオバマ大統領が一蹴したのを恨んでの行動では片付けられない理由ががあるのではないだろうか。独裁者が無謀な判断をしても、周囲が仲裁に入るのではないだろうか。

それとも、独裁者の無謀な判断を制止するメカニズムがないのだろうか。側近であっても独裁者に逆らうと命が危なくなる仕組みなのだろうか。そういうことが可能になるシステムは非常に不安定なものになるような気がする。

開戦の判断が独裁者の暴走でないのなら、開戦しないとどうしようもない国内事情が発生しているということなのだろうか。武装したままの兵士の脱走が増加しているという、原因は食料の欠乏だそうだ。欠乏しているとすれば今年の春の末には枯渇する危険がある。食料の調達が戦争しかなければしゃにむに仕掛けて来ざるを得なくなる。

同じような問題は中国にもある。水だ。軍隊に供給する水にも限りがでてきているようだ。

強大な専属の軍隊を持つことは、思いの外経費がかかる。現金があっても、資源の不足は賄えない。

中国人が日本の山林を買う動きが数年前から指摘されているが、安全保障のためにも、外国人に水源を押さえることのできないような仕組みを早急に法制化する必要があるのではないだろうか。
[PR]
by tnomura9 | 2013-03-30 08:52 | Haskell | Comments(0)

イニシエーション・ラブ

『イニシエーション・ラブ』 乾くるみ著 を読んだ。

恋愛小説なのかと思ったら、推理小説だった。

本の帯にもそう書いてあったし、指示通り順番どおりに読んで最後に「最後の2行」を読んだのに、最初、それが推理小説だったという意味がわからなかった。

悔しい ...

ええ、ええ、ちゃんと二回読みましたとも。
[PR]
by tnomura9 | 2013-03-28 09:06 | 話のネタ | Comments(0)

局所的最適化と大域的最適化

北朝鮮について不思議に思っていた事がある。経済政策の失敗による明らかな貧困状態にありながら、独裁政権の基盤は揺るがないように思われる。権力の維持という目的に対しては非常に巧妙なシステムが機能しているのだろう。権力の維持という目的に特化した局所的最適化だ。

しかし、その最適化は、どうも経済活動には良い影響を与えていないように思われる。貧困問題はいずれ国の存亡に関わってくるだろう。しかし、それがいつ来るのかはわからない。それくらい統治システムの最適化の力が強いという事だ。

とは言え、統治システムの最適化が国全体の経済力の阻害要因になっているとすれば、その安定性は大域的なシステムの破綻への重大な誘因になる。たとえは悪いが、がん細胞が細胞の増殖能力に特化して局所的な最適化を行った結果、徐々に個体の死滅を引き起こしていくいくようなものだ。

アベノミクスも今の所は目覚ましく機能しているように見える。しかし、それが日本の国全体としての繁栄をもたらす大域的な最適化であるのかどうかは常にモニターしておく必要があるだろう。北朝鮮や中国の問題は、川向こうの火事ではないかもしれないのだ。

局所的な最適化が大域的な最適化の強い阻害要因になるかもしれないという事だ。

技術力と海運や貿易力で繁栄を享受していたカルタゴ(フェニキア)がローマに滅ぼされ、その強大なローマの軍事力も滅亡を免れなかったように、中国も、米国も、そして日本も滅亡の危険は常にある事を忘れてはならない。

もし、中国と戦争になった場合、統一された中国と言う形態を残しては危険だという事だ。呉越やハンニバルの轍を踏んではならない。戦争における最適化とはそういうものだ。しかし、同じ事を中国も考えているだろう。尖閣問題が局地戦で済むという甘い期待は持たない方がいい。戦争になればいずれは総力戦になるだろう。

戦争は起きない方がいいのだ。
[PR]
by tnomura9 | 2013-03-27 07:41 | 話のネタ | Comments(0)

フェリチンと半導体

少し古い記事だが、ブックマークをひっくり返していて見つけた。読んでみたら分かりやすい文章で、とても面白かった。

タンパク質で作る半導体

赤血球には酸素を結合するためのヘモグロビンという物質が含まれているが、その材料に鉄イオンが使われる。その鉄を生体に貯蔵するためのタンパク質フェリチンを、半導体の上に金属の量子ドットを整列させるために使う研究だ。

フィリチンは12ナノメートルというウィルスの数分の1の大きさの中空の球体のタンパク質だ。そのなかの空洞に鉄を閉じ込めて貯蔵している。鉄は酸化鉄の形でフェリチンの内部に結合しているがその大きさは均一に7nmだ。これくらいの大きさになると、その原子に電子が1個はいるだけで、物性が変わってしまう。このような粒子を量子ドットという。

フェリチンを半導体の上に吸着させると、あらかじめ設計した形に大きさのそろった量子ドットを並べる事ができる。タンパク質に自己組織化の性質があるため、整列は自動的に行われる。半導体の上に整列したフェリチンを処理してタンパク質を除去し、さらに鉄の酸化物を取り除くと、整然と並んだ鉄の量子ドットを半導体の上に作る事ができる。

フェリチンを遺伝子操作の技術で作り変えると、鉄以外の金属の粒子の量子ドットも作る事ができる。

この方法を利用すると、切手一枚の大きさに1テラバイトのメモリーを構築できるらしい。

また、フェリチンは遺伝子操作で大腸菌に大量に作らせる事ができる。大量生産も可能なのだ。

原発事故だ、銀行の破綻だ、領土問題からの戦争だ、民族紛争だと憂鬱な記事が多い中で、夢を感じさせるニュースだ。
[PR]
by tnomura9 | 2013-03-25 07:28 | 話のネタ | Comments(0)

Yet Another Haskell Tutorial 解読

Yet Another Haskell Tutorial : Chapter 1-3
Yet Another Haskell Tutorial 2 : Chapter 4 Type Basics
Yet Another Haskell Tutorial 3 : 4.3 Type Classes
Yet Another Haskell Tutorial 4 : 4.4 Function Types
Yet Another Haskell Tutorial 5 : 4.5 Data Types
Yet Another Haskell Tutorial 6 : 4.6 Continuation Passage Style
Yet Another Haskell Tutorial 7 : 5 Basic Input/Output
Yet Another Haskell Tutorial 8 : 6 Modules
Yet Another Haskell Tutorial 9 : 7 Advanced Features
Yet Another Haskell Tutorial 10 : 7.4 Pattern Matching
Yet Another Haskell Tutorial 11 : 7.5 Guards
Yet Another Haskell Tutorial 12 : 7.6 Instance Declarations
Yet Another Haskell Tutorial 13 : 7.7 Datatypes Revisited
Yet Another Haskell Tutorial 14 : 7.9 Arrays
Yet Another Haskell Tutorial 15 : 7.11 Layout
Yet Another Haskell Tutorial 16 : 8 Advanced Types
Yet Another Haskell Tutorial 17 : 8.3 Datatypes
Yet Another Haskell Tutorial 18 : 8.4 Classes
Yet Another Haskell Tutorial 19 : 8.4.2 Computations
Yet Another Haskell Tutorial 20 : 8.5 Instances
Yet Another Haskell Tutorial 21 : 9 Monads
Yet Another Haskell Tutorial 22 : 9.1 Do Notation
Yet Another Haskell Tutorial 23 : 8.1 Do Notation (続き)
Yet Another Haskell Tutorial 24 : 9.2 Definition
Yet Another Haskell Tutorial 25 : 9.3 A Simple State Monad
Yet Another Haskell Tutorial 26 : 9.3 A Simple State Monad (続き)
Yet Another Haskell Tutorial 27 : 9.3 A Simple State Monad (続き2)
Yet Another Haskell Tutorial 28 : 9.3 A Simple State Monad (続き3)
Yet Another Haskell Tutorial 29 : 9.4 Common Monads
Yet Another Haskell Tutorial 30 : 9.4 Common Monads (続き)
Yet Another Haskell Tutorial 31 : 9.5 Monadic Combinators
Yet Another Haskell Tutorial 32 : 9.6 Monad Plus
Yet Another Haskell Tutorial 33 : 9.7 Monad Transformers
Yet Another Haskell Tutorial 34 : 9.7 Monad Transformers (続き)
Yet Another Haskell Tutorial 35 : 9.7 Monad Transformers (続きその2)
[PR]
by tnomura9 | 2013-03-21 19:16 | Haskell 記事リスト | Comments(0)

Yet Another Haskell Tutorial 35

9.7 Monad Transformers (続きその2)

やっと、YAHT 本文に挑戦する事ができるようになった。YAHT のこの節の記事の目的は、2つのモナド State モナドと IO モナドの機能を併せ持った合成モナド StateT モナドの使い方を説明する事だ。

端的に言うと、(YAHTの記事にはないが) なぜ次のプログラムが動くのかを理解する事だ。

Prelude> :m Control.Monad.State
Prelude Control.Monad.State> runStateT (do c <- get; lift(print (c*2))) 3
6
((),3)

上のプログラムでは State モナドの c <- get と IO モナドの print (c*2) が (lift 関数を介して) 混在している。これを実現するためには、State モナドの性質を持った StateT モナドを定義し、IO モナドを lift 関数によって StateT モナドに変換する(ラッピングする) という方法をとる。

lift 関数の型は次のようになる。

class MonadTrans t where
  lift :: Monad m => m a -> t m a

lift 関数はモナド値 m a を引数にとって、それを合成モナド t m a に変換する。ここで、間違えやすいのは t m a という記述でモナド値 m a がデータコンストラクタ t にラッピングされるというイメージを持ってしまうことだ。上の記述は単に引数と戻り値の型の関係を述べているだけで、ラッピングをしているわけではない。

lift 関数の実装は実際には次のようになる。

instance MonadTrans (StateT state) where
  lift m = StateT (\s -> do a <- m; return (s,a))

これを理解するためには、StateT 型の構造を知る必要がある。StateT 型は State モナドの性質を持つ必要があるので、まず、State 型を見てみよう。

newtype State state a = State (state -> (state, a))

上の newtype 宣言で分かるように、State 型データコンストラクタのパラメータは (state -> (state,a)) 型の関数だ。State 型の State モナドが状態を取り扱ためのしくみのポイントがこの関数の形のパラメータであることは、前回の記事で述べた。

それでは StateT 型の構造はどうだろうか。

newtype StateT state m a = StateT (state -> m (state, a))

StateT データコンストラクタのパラメータは (state -> m (state,a)) 型の関数だ。State 型の場合と似ているがペア (state, a) がモナド m のパラメータになっている所が違う。パラメータの値が、1引数で戻り値が (state,a) のペアになっているので State モナドの性質を持ち、戻り値が m (state,a) のモナド型なので IO モナドの性質も持つ事ができる。

そこで、lift 関数の実装をもう一度見てみよう。

instance MonadTrans (StateT state) where
  lift m = StateT (\s -> do a <- m; return (s,a))

これがどういう意味を持っているのか、lift (print "hello") と同じデータを作成してみるとわかる。

Prelude Control.Monad.State> :t (\s -> do a <- print "hello"; return (s,a))
(\s -> do a <- print "hello"; return (s,a)) :: t -> IO (t, ())

型を見ると、1引数で戻り値が IO (t, ()) 型の関数だ。そこで、状態 3 を引数として与えてみる。

Prelude Control.Monad.State> (\s -> do a <- print "hello"; return (s,a)) 3
"hello"
(3,())

また、引数が1個で戻り値が IO モナド値の関数は IO モナド型の関数だから、>>= 演算子で結合する事ができる。

Prelude Control.Monad.State> return "world" >>= (\s -> do a <- print "hello"; return (s,a))
"hello"
("world",())

こうして見ると、StateT (state -> m (state, a)) の StateT 型は、IO モナドを内部にラッピングしたデータ型というより、IO モナドに State モナドの機能を包含させたものと考えた方がよいような気がする。いつの間にか裏と表が入れ替わっていたという感じだ。

State モナドの記事にも書いたが、runState 関数は State 型のパラメータの runState フィールドへのアクセサ関数だ。State 型のパラメータの関数を取り出す働きがある。StateT モナドの場合も同様のアクセサ関数 runStateT がある。

Prelude Control.Monad.State> runStateT (do lift(print "hello")) 3
"hello"
((),3)

これは、runStateT 関数が StateT 関数のパラメータの関数を取り出す働きがあった事を考えると、このプログラムは次のプログラムと等価である。

Prelude Control.Monad.State> (\s -> do a <- print "hello"; return (s,a)) 3
"hello"
(3,())

StateT 型のパラメータの関数に引数を与えると、IO モナドが表に現れて実行されることが分かる。

なにか分かったような分からないような説明になってしまったが、StateT モナドを使う立場から言えば、次のように lift 関数で IO モナドが StateT モナドに埋め込まれるというイメージを持っていた方が便利だ。

Prelude Control.Monad.State> runStateT (do c <- get; lift (print c)) 3
3
((),3)

モナドのプログラムは普通 do 記法の中に書かれるが、do 記法は >>= 演算子によるモナドのプログラムのシンタックスシュガーにすぎない。StateT モナドの演算を可能にする return、>>=、fail の定義は次のようになる。

instance Monad m => Monad (StateT state m) where
  return a = StateT (\s -> return (s,a))
  StateT m >>= k = StateT (\s -> do
    (s', a) <- m s
    let StateT m' = k a
    m' s')
  fail s = StateT (\_ -> fail s)

>>= の定義が複雑だが、基本的には元の状態と値 (s, a) を取り出し、関数 k を作用させて、新しい状態と値 (s', a') をStateT でラッピングして返すという操作をしている。このコードは現在の Control.Monad.State.Lazy のコードとは違うので、これ以上は立ち入らない。

StateT モナドの関数には、State モナドに見られるような関数が定義されている。

getT :: Monad m => StateT s m s
getT = StateT (\s -> return (s, s))

putT :: Monad m => s -> StateT s m ()
putT s = StateT (\_ -> return (s, ()))

evalStateT :: Monad m => StateT s m a -> s -> m a
evalStateT (StateT m) state = do
  (s', a) <- m state
  return a

YAHT の残りの記事は StateT モナドの応用に関するものなので説明は省略する。

モナド変換子を終えて、YAHT に記述されているモナドの説明はほぼ網羅した。YAHT 山系の最高峰 Monads の山頂を踏破した事になる。あとは、モナドを応用したパーサの設計法の記事が残っているが、コンピュータネタの記事が長くなりすぎたのでちょっと疲れてきた。またまた、尻切れとんぼになってしまったが、YAHT の解読記事はこれで終わりにしたい。

Haskell の知識の整理のつもりで読み始めた YAHT だったが、途中から、初心者向けの分かりやすいチュートリアルなどではなくなってきた。しかし、おかげで継続の初歩や、モナドの基礎についての知らなかった知識が得られたのはよかった。ただ、Haskell 関係の本を読むのはかなりつらいものがある。それだけ、著者のバックグラウンドと自分のそれとの差が大きいのだろう。

ちょっと休憩。
[PR]
by tnomura9 | 2013-03-20 22:29 | Haskell | Comments(0)

Yet Another Haskell Tutorial 34

9.7 Monad Transformers (続き)

YAHT の本文を読む前にもう一つすることがある。それは State モナドのしくみを理解することだ。それには、自前の State モナドを作ってみるのが良い。次のプログラムをファイル名 MyState.hs で作成した。

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}

module MyState where

import Control.Monad.State

newtype MyState s a = MyState {runMyState :: (s -> (a, s))}

instance Monad (MyState s) where
  return a = MyState $ \s -> (a, s)
  m >>= k = MyState $ \s -> let
    (a, s') = runMyState m s
    in runMyState (k a) s'

instance MonadState s (MyState s) where
  get = MyState $ \s -> (s,s)
  put s = MyState $ \_ -> ((),s)

やっていることは、newtype 宣言で MyState s a 型を作る。データコンストラクタ MyState のパラメータはフィールド名付きで、(s -> (a,s)) 型の関数だ。つぎに Mystate s 型を Monad クラスのインスタンスに宣言し、return と >>= の実装を行う。最後に MyState s 型を MonadState クラスのインスタンスにして get, put が do 記法の中で使えるようにする。

ファイルの冒頭の言語オプションのプラグマは、プログラムをコンパイルするときにエラーメッセージで表示されたものをコンパイルエラーがなくなるまでおいてみただけだ。

面倒くさい解説をしても面白く無いので、さっそく動かしてみる。

Prelude> :l MyState.hs
[1 of 1] Compiling MyState ( MyState.hs, interpreted )
Ok, modules loaded: MyState.
*MyState> runMyState (do c <- get; put (c+1)) 2
((),3)

動いた。動かす側から見る MyState モナドの理解は runMyState の働きをみることから始まる。runMyState の型は次のようになる。

*MyState> :t runMyState
runMyState :: MyState s a -> s -> (a, s)

つまり runMyState は MyState 型の引数を第1引数にとり、s 型の状態の値を第2引数にとり、a 型の値と s 型の状態の値とのペアを返す関数だ。

上のプログラムでは runMyState の定義はないのに何故?という疑問がわくが、それは MyState 型のパラメータが runMyState というフィールド名を持っているために、自動的に設定されるアクセサー関数が runMyState になるためだ。

たとえば、m という値が MyState モナドのとき、runMyState m は第1引数が s 型で、戻値が (a,s) 型の関数になる。上の実行例は (runMyState (do <- get; put (c+1))) という関数を数値 2 に関数適用することで ((), 3) つまりモナドのパラメータが () で、状態が 3 であることを示すペアが値として返される。

モナドのプログラムは、runMyState の第1引数として与えられるが、do 記法のプログラムの型でわかるように、MyState モナドの値だ。

*MyState> :t (do c <- get; put (c+1))
(do c <- get; put (c+1)) :: (Num s, MonadState s m) => m ()

do 記法では do c <- get; put (c+1) のようにセミコロンで区切って次々にモナド型の関数をつないでいくことができる。MyState モナド型の関数は put の型からわかるように、s -> m a 型の関数つまり、引数がひとつで、値が MyState モナド値の関数だ。

*MyState> :t put
put :: MonadState s m => s -> m ()

自前の MyState モナド型の関数は return 関数を使うことで簡単に作ることができる。上の実行例にreturn 関数を利用した自前のモナド型関数を加えると次のようになる。

*MyState> runMyState (do c <- get; put (c+1); return $ "new count = " ++ show (c+1)) 2
("new count = 3",3)

MyState 型で話を進めてきがた、これらの性質は State モナドの性質と同じだ。そこで、最後に、 State モナドについての要点をまとめてみる。

  1. Stateモナドのプログラムは、do 記法の中に記述する。do 記法の中ではセミコロンで区切って、あるいは適切なインデントで1行ずつ、State モナド型の関数を結合していくことができる。
  2. Stateモナド型の関数とは引数が1つで戻値が State 型の値の関数 a -> State s a である。
  3. State モナドの値は、パラメータつきデータコンストラクタ State {runState :: (s -> (a,s))} である。
  4. runState 関数は、State データコンストラクタのパラメータのフィールド "runState" へのアクセサ関数である。
  5. Stateモナドのプログラムの実行はまず、 runState 関数を do 記法で作成した Stateモナド値に関数適用することで、Stateモナドのフィールドの s -> (a,s) 型の関数をとりだす。さらに、その関数を状態の初期値に関数適用するという2段構えで行われる。あるいはもっと簡単に runState 関数を第1引数が State モナド値で第2引数が状態の初期値の関数 runState :: State s a -> s -> (a,s) と考えてもよい。


State モナドを説明するのに、わざわざ MyState モナドを作成したのは、State モナドのしくみをブラックボックスにしないためだった。State モナドの内部構造を理解していれば State モナドの合成モナドである StateT モナドの意味がわかりやすくなる。

Yet Another Haskell Tutorial 35 へ続く ...
[PR]
by tnomura9 | 2013-03-20 12:00 | Haskell | Comments(0)

Yet Another Haskell Tutorial 33

9.7 Monad Transformers

このセクションはモナド変換子についての説明だ。一通り読んでもなかなか理解できない。しかし、実のところは合成モナドの StateT の使い方を説明しているだけだ。

大雑把にいうと、モナドのプログラムは do 記法の中に、「モナド型の関数」を並べていく事で行われる。次の例は IO モナドの場合だ。

Prelude> do cs <- getLine; putStrLn cs
hello
hello

また、次の例は State モナドの場合だ (State モナド)。

Prelude> :m Control.Monad.State
Prelude Control.Monad.State> runState (do c <- get; put (c+1)) 1
((),2)

この2つの例で分かるように、モナドのプログラムを do 記法の中に記述したり、>>= 演算子で結合したりするためには、結合する関数は全てそのモナドの「モナド型関数」でなければならない (IO モナドの正体)。

したがって、上の例でも、IO モナドの do 記法の中には IO モナド型の関数しか現れないし、State モナドの do 記法の中の関数も全て State モナド型の関数だ。

このような理由で、手続き型言語に見られるような変数の値を端末に打ち出す printf デバッグを Haskell のプログラムの中で行うことはできない。

ところが、State モナドの合成モナドである StateT モナドを使うと、lift 関数の中で IO モナドの関数を使うことができる。言葉による説明では分かりづらいので次の例を見てみよう。

Prelude Control.Monad.State> runStateT (do c <- get; lift (print c); put (c+1); c <- get; lift (print c)) 1
1
2
((),2)

こうすれば、簡単に State モナドの中で IO モナドの関数を使うことができる。つまり、lift 関数で IO モナド型の関数 print をラッピングしてやることで、これを StateT モナド型の関数として使うことができるのだ。このように、合成モナドの StateT は使い方は非常に簡単だ。しかし、それを実現するための仕組みの説明になると途端に難しくなる。

Yet Another Haskell Tutorial 34 へ続く ...
[PR]
by tnomura9 | 2013-03-19 07:52 | Haskell | Comments(0)

Yet Another Haskell Tutorial 32

9.6 Monad Plus

モナドのアクションを結合させる方は bind 演算子 (>>=) 以外に mplus 演算子がある。どちらも2つのアクションを結合して新しいアクションを生成する方法なので混同しやすいが、>>= 演算子の型は、

Prelude> :t (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b

で、malus 演算子の場合は、

Prelude> :m Control.Monad
Prelude Control.Monad> :t mplus
mplus :: MonadPlus m => m a -> m a -> m a

なので、第2引数が >>= では (a -> m b) 型の関数であり、mplus では m a 型のアクションであるところが違っている。もちろん、意味も違う。

mplus を使うためには、目的のデータ型が MonadPlus (タイプ)クラスのインスタンスである必要がある。MonadPlus (タイプ)クラスの多相関数は2つあり、mzero と mplus だ。

Prelude Control.Monad> :info MonadPlus
class Monad m => MonadPlus m where
mzero :: m a
mplus :: m a -> m a -> m a
-- Defined in `Control.Monad'
instance MonadPlus [] -- Defined in `Control.Monad'
instance MonadPlus Maybe -- Defined in `Control.Monad'

数学的には、アクション m a と mzero と mplus の3つ組はモノイドをなしている。リスト型と Maybe 型は既に MonadPlus (タイプ)クラスのインスタンスだ。

こういう小難しい説明がなくても mplus の威力は例題プログラムを実行すると知ることができる。以下は、YAHT の例題プログラムを追っかけていく。

YAHT では、先ず Maybe 型と List 型における mzero と mplus の実装が紹介してある。

最初に Maybe 型について見てみる。

instance MonadPlus Maybe where
  mzero = Nothing
  mplus Nothing y = y
  mplus x _ = x

この動作を ghci で確認すると次のようになる。

Prelude Control.Monad> mzero :: Maybe Int
Nothing
Prelude Control.Monad> Nothing `mplus` Just 1
Just 1
Prelude Control.Monad> Just 1 `mplus` Just 2
Just 1
Prelude Control.Monad> Just 1 `mplus` Nothing
Just 1

Maybe 型のアクション Maybe a は大抵は検索値なので、Maybe a `mplus` Maybe a は最初の検索がヒットした場合はその値を戻し、最初の検索がヒットしなかった場合は二番目の検索の結果を戻すという意味になる事が多い。

次にリスト型について見てみる。

instance MonadPlus [] where
  mzero = []
  mplus x y = x ++ y

リスト型の mplus の意味は、単にリストの連結だ。

Prelude Control.Monad> mzero :: [Int]
[]
Prelude Control.Monad> [1,2] `mplus` [3,4,5]
[1,2,3,4,5]

これだけでは、ありがたみがあまり感じられないが、YAHT では前セクションで例示した searchAll 関数を改造して、グラフの経路検索に mplus を使う事で経路を全て検索できるように searchAll2 関数を作ってみせている。ghci で実験できるように次のプログラムをファイル searchAll2.hs に作成した。

import Control.Monad

data Graph v e = Graph [(Int, v)] [(Int,Int,e)]
  deriving Show

searchAll2 g@(Graph vl el) src dst
  | src == dst = return [src]
  | otherwise = search' el
  where
    search' [] = fail "no path"
    search' ((u,v,_):es)
      | src == u =
          (searchAll2 g v dst >>= \path ->
           return (u:path)) `mplus`
          search' es
      | otherwise = search' es

gr = Graph [(0,'a'),(1,'b'),(2,'c'),(3,'d')]
           [(0,1,'l'),(0,2,'m'),(1,3,'n'),(2,3,'m')]

gr2 = Graph [(0,'a'),(1,'b'),(2,'c'),(3,'d')]
            [(0,1,'l'),(0,2,'m'),(2,3,'m')]

searchAll 関数と searchAll2 関数の違いは search' 関数の定義に `mplus` search' es が付け加えられているところだけだ。

ghci で検証してみた。

Prelude> :l searchAll2.hs
[1 of 1] Compiling Main ( searchAll2.hs, interpreted )
Ok, modules loaded: Main.
*Main> searchAll2 gr 0 3 :: [[Int]]
[[0,1,3],[0,2,3]]
*Main> searchAll2 gr2 0 3 :: [[Int]]
[[0,2,3]]

セクション 9.4 の searchAll 関数では1つの経路の検索しかできなかったが、searchAll2 関数では全ての経路の検索ができる。また searchAll 関数で検索できなかったグラフ gr2 の経路も検索できるようになった。

searchAll2 関数は Maybe モナドでも使えるが、Maybe モナドの mplus 関数にはリストを連結する意味がないので、最初に検索が成功した経路のみが返される。しかし、searchAll の時と違って gr2 のグラフの経路検索にも成功する。

*Main> searchAll2 gr 0 3 :: Maybe [Int]
Just [0,1,3]
*Main> searchAll2 gr2 0 3 :: Maybe [Int]
Just [0,2,3]

例題のプログラムを実行して、mplus では何かすごい事をやっているのだなと実感する事ができる。しかし、それを理論的に理解しようとすると数学的な基礎が必要になってくるだろう。とにかく、例題のプログラムを参考にいろいろと使っているうちに、操作的に理解できればプログラムは作る事ができるし、mplus のパワーを利用できる。

Yet Another Haskell Tutorial 33 へ続く
[PR]
by tnomura9 | 2013-03-17 09:11 | Haskell | Comments(0)