<   2013年 07月 ( 16 )   > この月の画像一覧

All About Monads 読解 19

Monad transformers

monad transformer は標準モナドの変種だが、複数のモナドを関連づけることができる。monad transformer のパラメータは、モナドタイプコンストラクタだ。したがって、これは、複合モナド型になる。

Transformer type constructors

Hakell のモナドでは、タイプコンストラクタが重要な役割を持っている。例えば Reader モナドの場合、Reader r a タイプコンストラクタは、a 型の値と r 型の環境で構成されている。タイプコンストラクタの Reader r は Monad クラスのインスタンスだ。そうして runReader :: r -> a は ReaderT モナドのモナド値のコンテナの値で、 a 型の値を返す処理(関数)だ。

transformer バージョンの Reader モナドは ReaderT である。これは Reader モナドのパラメータに加えて、m 型のパラメータをとる。ReaderT r m a は複合もモナドだ。ベースのモナドは Reader で、m はその内側のモナド inner monad だ。ReaderT r m はモナドクラスのインスタンスで、runReaderT :: (r -> m a) は複合モナドのモナド値のコンテナの値で、m a を返す関数だ。

transformer バージョンのモナドを使えば、簡単に複合モナドを拵えることができる。Reader r IO は、Reader + IO の複合モナドだ。複合モナドから、基本的なモナドを作るのは簡単で、Identity モナドを m に当てはめればいい。したがって、ReaderT r identity は Reader r と同じモナドである。

注意!:自作のプログラムが kind エラーになったときは、タイプコンストラクターを適切に用いてないからだ。その場合、タイプコンストラクターに適切な数のパラメータを使っているかどうか、複合タイプの記述に適切な括弧が入れてあるかを確認する必要がある。

Lifting

monad transformer でつくられた複合モナドを作る場合、タイプコンストラクタの内側のモナドを使うのに、そのモナドを直接的に指示する必要はない。そのため、クリアでシンプルなコードを書く事ができる。前回のプログラムで見たように、モナドの do ブロックの中でさらに別のモナドの do ブロックを記述するのではなく、内側のモナドを lift する事によって、複合モナドの do ブロックの中で使う事ができる。

liftM ファミリーの関数が普通の関数をモナドの関数にする機能がある事を思い出してほしい。monad transformer には lift 関数がある。lift 関数はモナドの関数を複合モナドの関数に変える。また、多くの transformer は liftIO 関数を持っている。この関数は lift 関数の機能を持つが、引数に IO モナドの関数をとり、IO モナドの関数を複合モナドにリフトするために特化している。liftIO の働きを見るために、以前に用いた継続モナドのプログラムを改変してみよう。

fun :: IO String
fun = (`runContT` return) $ do
        n   <- liftIO (readLn::IO Int)
        str <- callCC $ \exit1 -> do     -- define "exit1"
          when (n < 10) (exit1 (show n))
          let ns = map digitToInt (show (n `div` 2))
          n' <- callCC $ \exit2 -> do    -- define "exit2"
            when ((length ns) < 3) (exit2 (length ns))
            when ((length ns) < 5) $ do liftIO $ putStrLn "Enter a number:"
                                        x <- liftIO (readLn::IO Int)
                                        exit2 x
            when ((length ns) < 7) $ do let ns' = map intToDigit (reverse ns)
                                        exit1 (dropWhile (=='0') ns')  --escape 2 levels
            return $ sum ns
          return $ "(ns = " ++ (show ns) ++ ") " ++ (show n')
        return $ "Answer: " ++ str

ContT 複合モナドを使う事で、Cont モナドのプログラムを改変せずに、IO モナドの関数を埋め込むのに成功している。直接に do ブロックを埋め込んで同じような機能を実現した前回のプログラムと比べると、その簡明さが分かる。

上のプログラム example21.hs はコピペで動作確認できる。ただし、import の部分を次のように書き換える必要がある。

import System.IO
import Control.Monad
import System.Environment
import Data.Char
import Control.Monad.Cont

実行例は次のようになる。

*Main> :l example21.hs
[1 of 1] Compiling Main ( example21.hs, interpreted )
Ok, modules loaded: Main.
*Main> :main
2002
Enter a number:
3
Answer: (ns = [1,0,0,1]) 3

liftIO の使い方を確認してみた。

Prelude> import Control.Monad.Cont
Prelude Control.Monad.Cont> runContT (do x <- liftIO (readLn :: IO Int); return x) (\x -> print (x*2))
5
10
Prelude Control.Monad.Cont> :t runContT (return 2)
runContT (return 2) :: Num a => (a -> m r) -> m r

ContT 複合モナドの中に IO モナドを埋め込むには単に liftIO の引数にIOモナドの関数を渡してやればいい事が分かる。runContT の型は (a -> m r) -> m r なので、引数には型 a をとり IO r を返すような関数を割り当ててやればいい。上の場合だと (\x -> print (x*2)) がその関数だ。

前へ 目次 次へ
[PR]
by tnomura9 | 2013-07-31 22:56 | Haskell | Comments(0)

中国マネー引き上げの影響

7月31日付の『NEWSポストセブン』のウェブに「中国マネーが日本から引き上げれば不動産下落しデフレ再来も」という記事が掲載されていた。

中国の「陰の銀行」が破綻した場合、日本もその影響を免れないようだ。

記事によれば、アベノミクス以降の株高は、海外マネーの流入によるものが大きく、その中でも、中国マネーの比率が高いそうだ。銀座、六本木、赤坂などの一等地を買いあさっているのは中国マネーらしい。中国のバブル崩壊が起きれば、中国マネーは日本の不動産から引き上げ、土地価格の下落、デフレと進む可能性がある。

また、中国ファンドや、中国株に投資している投資家は直接的な被害を受けるだろう。さらに、中国での販売成績に依存している企業も影響を免れない。

中国経済が崩壊した時、日本が無傷ということはありえないだろう。

金融崩壊の恐ろしさは、それが、実体経済の状況にかかわらず、風聞やムードといった掴みどころのないものにも影響を受けるということだ。アメリカの不動産バブルの崩壊がメディアの報道をきっかけに起こったということは記憶に新しい。したがって、欧米の一流のメディアが中国の経済危機を報道し始めたということは、欧米の投資家に中国沈没への準備が完了したということを意味していると考えるのは深読みしすぎだろうか。

我々庶民には無縁の話だが、それでも何か準備が必要なのだろうか。
[PR]
by tnomura9 | 2013-07-31 18:27 | 話のネタ | Comments(0)

江蘇省の財政破綻

7月25日付けのロイター日本語版のウェブの記事によると、中国江蘇省の財政状態が非常に悪いらしい。原因は、造船、太陽光発電パネルなどの過剰生産による不振で、税収が激減して地方政府の負債が膨らんでいる。中央政府の投資依存への規制の方針の打撃を、江蘇省の財政は最も受けやすい体質だ。

江蘇省域内のGDPはトルコを抜き世界の上位20カ国に食い込み、人口は7900万人と大半の欧州諸国を上回る。これが、財政破綻をしたら中国全体にも大きな影響があるだろう。

不気味なのは、ロイターのような欧米の報道機関が、この事実を取り上げ始めたという事だ。破綻説のあった7月はもう終わろうとしているが、予断をゆるさない。
[PR]
by tnomura9 | 2013-07-29 07:38 | 話のネタ | Comments(0)

圏論の言葉 その2

endomap

endomap は domain と codomain が同じ射だ。そう珍しいものではなく、整数の集合を domain とし、整数の2倍の値を返す関数(射)は、codomain が整数になる。

Prelude> :set +m
Prelude> let
Prelude| double :: Int -> Int
Prelude| double x = 2 * x
Prelude|
Prelude> double 3
6

有限個の数値の集合の endomap のうち、全単射になるものは、順列だ。

Prelude> let
Prelude| f 1 = 4
Prelude| f 2 = 3
Prelude| f 3 = 2
Prelude| f 4 = 1
Prelude|
Prelude> map f [1,2,3,4]
[4,3,2,1]

identity map

endomap のうち、関数の値が引数と同じものになるものを identity map という。Haskell では id と定義されている。

Prelude> id 1
1
Prelude> id [1,2]
[1,2]

対象 A の identity map は domain と codomain が共に A なので、 1A と表される。任意の関数(射) f と identity map との合成 (composition) について次の identity laws が成立する。つまり、f :: A -> B, g :: B -> C のとき、

1B . f = f
g . 1B = g

である。ghci で試すと次のようになる。

Prelude> map (id . (*2)) [1,2,3]
[2,4,6]
Prelude> map (id . (*2)) [1,2,3] == map (*2) [1,2,3]
True
Prelude> map ((*2) . id) [1,2,3]
[2,4,6]
Prelude> map ((*2) . id) [1,2,3] == map (*2) [1,2,3]
True

関数が f :: A -> B 一つだけのときは、identity laws は、f . 1A = f, 1B . f = f である。

point

要素が1つだけの集合を singleton set といい、1 で表す。Haskell では () で表され、unit type と呼ばれる。singleton set から集合 A への関数を point という。point の値は codomain の1つの要素になる。

Prelude> let
Prelude| point :: () -> Int
Prelude| point () = 3
Prelude|
Prelude> point ()
3

point は関数なので他の関数と合成することができる。

Prelude> ((*2) . point) ()
6

圏論を学ぼうと思ったら、こんな基礎的な用語の理解からはじめないとダメなようだ。無茶苦茶時間がかかるのは覚悟しないといけない。たとえば、identity low など、当たり前のことのように感じるが、関数合成の代数 The algebra of composition の話になってくると重要な役割を果たしていることがわかる。

また、point は集合の要素の一個を関数で表現したものだが、集合の全射や、単射を圏論の言葉で扱うときに重要になる。圏論の枠組みは集合には限定されないので、集合における全射や単射を圏論の言葉で表現しておくと、集合の圏以外の圏にも対応させることができる。

たとえば singleton set から集合 A へは集合 A の要素の数だけの point が存在する。この point を考慮に入れると f :: A -> B, g :: A -> B があったとき f == g となる条件は、

全ての point p について、f . p = g . p である

というように、map だけで map f と g が等しい事を定義できる。

いつモナドに辿り着けるのか、あるいは果たしてたどり着けるのかどうかさえも分からないが、しかし、地道に足元を固めるしかない。
[PR]
by tnomura9 | 2013-07-27 19:39 | 圏論 | Comments(0)

中国のバブル崩壊のタイミングと Google トレンド

7月26日付けの、eワラント証券株式会社のレポート「中国のシャドーバンキング問題とバブル崩壊のタイミング―Googleトレンドを用いた投資分析―」によると、メディアのシャドーバンキングについての報道記事の増加が、中国の不動産バブル崩壊の予測に役立つかもしれないとのことだ。

同レポートの主張では、米国のサブプライムローンの例を取り上げている。サブプライムローンの問題がメディアに取り上げられ始めた最初の頃は株価は堅調だった。しかし、その後株価の急落がおこると、メディアの報道がサブプライムローン一色となり、その後発生したリーマンショックで株価はさらに下落した。

これは、投資リスクをメディアの報道で感知した投資家が、投資を現金化してリスクを低減させようとしたためだ。株価が下がる前に現金化しないといけないので、株の売却は他の人より先に行わないといけない。様子見の時期からトレンドがはっきりと株価下落の様相を呈すると、争って株の売却が行われ、株価の危機的な下落が起きる事になる。メディアの報道が、バブル崩壊の原因の明白な一員であることをこのレポートは主張している。

中国のシャドーバンキングの報道量は Google トレンドをみると、最近激増しており、リーマンショックのときのパターンに類似している。このレポートでは、「今後半年程度以内に株価の急落が起こり、その後メディアがシャドーバンキング一色に、さらにその後大型倒産 を含む本格的なバブル崩壊、というシナリオが考えられる。」として、長期の投資の買いポジションをとらず大部分を現金で残しておいて一部の資金でリスクをとることを勧めている。

なぜ、最近景気の変動が危機的に変化しやすいのだろうかと不思議に思っていたが、結局、比較的少数の投資家の行動を反映しやすいのがその理由だったのだ。多くの個人の行動の結果が平均化されてしまえば、大きな変動は起きにくい。しかし、少数の個人の行動が直ちに株価などに反映すれば、変動の幅が大きく変化が急激になりやすいのは理解できる。

また、投資家の情報源が様々であれば行動は均一にならないだろうが、彼らが一律にメディアの報道を判断材料にしていれば、同一行動をとる可能性が高くなるだろう。

経済の安定化をはかるためには、このメディアの報道と投資家の行動の同期という不安定要因を安定化させる何らかの仕組みを考える必要があるのではないだろうか。

たとえば、株式を原則無配当にするというのはどうだろうか。投資家は株の利益ではなく、投資先の営業の実際の内容を重視するようになる。したがって、投資がより実体経済にそったものになるだろう。また、実力を持った中小企業の株の非公開も考えられる。これによって、資金力が相場の変動に影響される事がなくなる。高度な社会福祉もそうだ。相続財産が3代で消滅すれば投資家が減少し、汗水たらして実体経済で仕事をする人が増える。貧富の格差が減れば、購買力の変動が薄められ、物価の変動がなくなる。

これらのアイディアは少々行き過ぎだし、内部矛盾や副作用を発生する可能性をもっているが、投資行動に対する何らかの緩衝機構を考えることは国の安全保障の上でも重要なことだと思う。
[PR]
by tnomura9 | 2013-07-27 07:29 | 話のネタ | Comments(0)

圏論の言葉

Haskell を勉強し始めて IO モナドなんかに出くわさなければ圏論など近づこうともしなかっただろうが、モナドを正確に理解したくなって、圏論の入門書 Conceptual Mathematics: A First Introduction to Categories F. William Lawvere、 Stephen H. Schanuel を読み始めた。高校卒業程度の予備知識でも読めるように懇切丁寧に書かれているのがうれしい。

しかし、圏論は圏論なので、そう簡単に理解できるようには思えない。そこで、分かったと思えたところをまとめてみる事にした。

圏論は適用範囲が広い抽象的な考え方なので、具体的なイメージが作りにくい。やはり、慣れ親しんだ集合と写像を使える「集合の圏」から始めた方が良いようだ。集合と写像を、対象と射として取り扱う事によって、他の圏に対してもイメージを広げていく事ができるのではないだろうか。ということで、以下では集合と写像からなる集合の圏について考えることにする。

圏には2つの要素がある。対象と射だ。集合の圏でいえば、対象は集合で射は集合から集合への写像になる。対象と射がどのような性質を持つものかは分からないでも、集合と写像ならイメージできる。

集合 A と 集合 B があって、集合 A から集合 B への写像 f があるとする。これが、圏であるためには、関数 f の domain が 集合 A で、codomain が集合 B でなければならない。

このとき、domain である集合 A のどの要素に対しても関数 f が定義されている必要がある。つまり、集合 A は関数 f の定義域である必要がある。なぜなら、圏では射の合成が定義できなければならないが、写像 g と f の合成 g . f がいつでも定義されるためには、g はその domain の全ての値に対して定義されていなければならないからだ。

しかし、codomain である集合 B の場合は関数の値域である必要はない。関数 f による集合 A の像が集合 B の部分集合である必要はあるが、codomain である集合 B と f(A) が一致する必要はない。ここのところが分かっていないと、後で述べる section や retraction の意味が分からなくなる。

また、写像の定義から 集合 A の要素 a の関数 f による像 f(a) は一つだけで(もちろん集合 B の要素であるが)f(a) = {b1, b2} のような対応の仕方はしない。

このように見てくると集合と写像を「集合の圏」にするための制約が結構多いことがわかる。この基本的な制約から「集合の圏」の性質を調べていかなければならないのだが、集合と写像といったり、対象と射と言ったりするとなかなか面倒なので、これ以後は対象と射という用語で統一する事にする。

集合の圏の定義が上のようであれば、対象 A から 対象 B への射 f と対象 B から 対象 C への射が g である場合射の合成 g . f ができて、これは 対象 A から 対象 C への射となる。つまり、

f : A -> B かつ g : B -> C のとき、g . f : A -> C

を考える事ができる。このとき、f は B への全射でなくてもいいが、g の定義域は B である必要がある。つまりどの B の要素にも g が定義されている必要がある。

集合の間の写像が圏の射であるためには、さらに制約がでてくる。それは、射の合成が結合法則に従う必要があるという事だ。つまり、

f : A -> B, g : B -> C, h : C -> D のとき

h . (g . f) = (h . g) . f

が成り立つということだ。したがって、射の合成の結果はその合成の順序によらないから、

h . (g . f) = h . g . f

のように括弧を外して使う事ができる。

なぜ結合法則が大切かというと、例えば、射 g についてその逆方向の射 i : C -> B があって i . g = idB だったとする。idB は対象 Bのどの要素についてもその要素自身を対応させる写像だ。つまり x を対象 B の要素だとすると、idB (x) = x であるということだ。Haskell では単に id と定義されている。

そうすると次のように合成射の縮約ができる。

i . (g . f) = (i . g) . f = idB . f = f

このように、射の合成に関して演算を施す事ができるためには、どうしても結合法則が必要なのだ。

idB については特に説明せずに使ったが、これは対象 B から対象 B への恒等射で B の全ての要素 x について idB (x) = x となるようなものである。このような idB に対して、

idB . f = f および g . idB = g 、ただし、f : A -> B, g : B -> C

が成り立つ。

今までの議論をもっと定式的に述べるために、圏論の Wikipedia の記述を抜粋すると次のようになる。

圏(category)[1] は、射(morphism,map,arrow)と対象(object)と呼ばれる2種の集団からなる。

圏 C の射 f は必ずドメイン(domain)、余ドメイン(codomain)と呼ばれる C の対象が割り当てられている。 A が f のドメイン dom(f) = A かつ B が f の余ドメイン codom(f) = B であるとき f : A → B と表記する[2]。 圏の射について以下が成り立つ

射の合成演算(composite operator)’・’の存在
C の射 f , g in C について、dom(g) = codom(f) ならばそれらの合成 g・f in C が唯一つ存在する

結合律(associative law)
合成射 h・g , g・f が存在するとき、
h・(g・f) = (h・g)・f
がいつでも成り立つ。

単位元律(unit law)
ドメインと余ドメインが同一の射 1B : B → B が存在し、任意の射の合成について
1B・f = f かつ g・1B = g ただし、f : A → B , g : B → C
が成り立つ。1B のような各対象に対して割り当てられ、上記性質を持つ射を恒等射(identity)と呼ぶ。

上のように簡潔に書かれた圏の定義が、具体的な集合の圏になると、結構制約が多く、細かい所に注意が必要になる事がわかる。

ところで、Haskell の記法は圏を記述するのに便利だ。たとえば、関数の型のシグネチャー、

square :: Doublle -> Double

というのは、圏論風に表現すると、射 square は対象 Double から対象 Double への射であるということができる。実際、Haskell のプログラムは、データ型を対象とし、関数を射とする圏である。したがって、圏論で述べられる様々な定理は、そのまま Haskell のプログラムにも適用される。

したがって、Haskell を使って、圏の性質を実験することができる。たとえば上の単位元律を使った合成射の縮約は次のように実験できる。

Prelude> let f = (*2)
Prelude> let g x = x + 1
Prelude> let h x = x - 1
Prelude> map f [1,2,3]
[2,4,6]
Prelude> map g [1,2,3]
[2,3,4]
Prelude> map h [2,3,4]
[1,2,3]
Prelude> map (h.g) [1,2,3]
[1,2,3]
Prelude> map (h. g. f) [1,2,3]
[2,4,6]
Prelude> map (id .f) [1,2,3]
[2,4,6]

理論的なものを実験で確かめる事ができれば、理論のイメージを作るのがずいぶん楽になる。
[PR]
by tnomura9 | 2013-07-26 03:09 | 圏論 | Comments(0)

All About Monads 読解 18

Part III - Introduction

All about monads のパートIではモナドの考え方について、パートIIでは Haskell 標準のモナドについて解説されていた。しかし、実際には State モナドで状態を利用しながら I/O モナドを使いたいなど、モナドを混在させて使いたい場合が頻繁にある。Part III ではこのような場合に用いる monad transformer について解説されている。

Combining monads the hard way

複数のモナドを組み合わせて使いたいときに monad transformer を使う事になるが、その前に、monad transformer を使わないで、直接プログラムする方法を考えてみよう。そうすることで、複数のモナドを組み合わせて使う際の基本的な考え方や、monad transforer を使う利点がわかる。例示プログラムでは、contiuation monad の例示プログラム example18 を IO モナドと組み合わせる方法を考える。(example18.hs の動かし方は All Monads 読解 17 に説明している。)

Nested Monads

プログラムによっては、モナドがきれいにネストしていて、複合モナドを使わなくても良い場合がある。Haskell では全ての処理はトップレベルの IO モナドの中で行われる。したがって、今までに紹介したモナドのプログラムは、ネストしたモナドの計算のテクニックを使っていたことになる。これが行える条件は、外部入力の処理が、プログラムの先頭にかたまっていて、-- 大抵はコマンド・ライン引数を読み込むことになるが -- それをモナドのプログラムに与えて、得られた結果を最終的に出力プログラムに渡すという形式になる。この方法をとれば、複数のモナドを組み合わせる面倒はない。しかし、これは例示プログラムの example19.hs のようにやや不自然なプログラムになる。

example18 に導入された例示プログラムの example19.hs はこのネストしたモナドのパターンを利用している。IOモナドの中でコマンド・ラインから読み込まれた数値は、継続モナドに渡されて処理され文字列が帰ってくるが、その文字列は IO モナドの中で端末に印刷される。IO モナドの中での入出力のプログラムは継続モナドの影響は受けないので自由に記述できる。同様に継続モナドの中では、IOモナドを意識せずに複雑なプログラムを自由に記述できる。内側のモナドのプログラムが、外側のIOモナドの機能を利用しない限り、そのモナドはIOモナドの中で安全にネストすることができる。例示プログラムの example19.hs ではネストしたモナドのプログラムのバリエーションを示している。このブログラムではコマンド・ライン引数からではなく標準入力から数値をするようになっている。

fun :: IO String
fun = do n <- (readLn::IO Int)         -- this is an IO monad block
         return $ (`runCont` id) $ do  -- this is a Cont monad block
           str <- callCC $ \exit1 -> do
             when (n < 10) (exit1 (show n))
             let ns = map digitToInt (show (n `div` 2))
             n' <- callCC $ \exit2 -> do
               when ((length ns) < 3) (exit2 (length ns))
               when ((length ns) < 5) (exit2 n)
               when ((length ns) < 7) $ do let ns' = map intToDigit (reverse ns)
                                           exit1 (dropWhile (=='0') ns')
               return $ sum ns
             return $ "(ns = " ++ (show ns) ++ ") " ++ (show n')
           return $ "Answer: " ++ str

管理人注:

2つのモナドを混在させて使うのではなく、IO モナドの中に contiuation monad を埋め込んでしまう事ができる場合がある。example19.hs がその例だ。continuation モナドの結果をまるまる IO モナドの return 関数の引数として渡してしまうので、IO モナドの中に Cont モナドを埋め込んでしまう事ができる。

example19.hs はコピペで実行できるが、import の部分を次のように置き換える必要がある。

import System.IO
import Control.Monad
import System.Environment
import Data.Char
import Control.Monad.Cont

実行例

Prelude> :l example19.hs
[1 of 1] Compiling Main ( example19.hs, interpreted )
Ok, modules loaded: Main.

*Main> :main
20002
Answer: 10001

example19.hs の例は少し複雑なので端的な例を次に示す。

Prelude> import Control.Monad.Cont
Prelude Control.Monad.Cont> putStrLn $ runCont (return (2::Int)) show
Loading package transformers-0.3.0.0 ... linking ... done.
2

putStrLn は IO モナド、runCont ... は継続モナドだから、上のプログラムは2つのモナドを利用している。しかし rumCont ... から IO モナドの関数は呼び出されないので、何の問題もなくネストした継続モナドの結果を IO モナドで利用できている。

Combined Monads

複数のモナドを使うプログラムがもっと複雑な場合はどうしたら良いだろうか、単純なモナドのネストが使えないときは、2個以上のモナドを含む複合モナドを作る必要がある。これは1つのモナド値が他のモナド値のコンテナに入っているようなモナド値を作る必要がある。例えば、継続モナドと IO モナドを混在させるために Cont (IO String) のように継続モナドのモナド値のコンテナに、IOモナドのモナド値を入れる場合がある。また状態モナドのモナド値のコンテナにエラーモナドを入れて State (Either Err a) のような複合モナドを作り、状態モナドとエラーモナドの特性の両方を扱うことができる。

例示プログラムを少し改変してみよう。上のプログラムと同じように最初に IO モナドで処理を行うが、継続モナドの中からもIOモナドの関数で端末からの入力ができるようにする。この場合、最初の入力値が3桁以上5桁
未満の場合、プログラムの中から値を変更することができる。継続モナドの中の処理と、IOモナドの処理とが相互に依存しているため、ネストしたモナドのプログラム・パターンは使えない。

下の例示プログラムでは、IOモナド値を継続モナド値のコンテナに入れる方法は取っていない。その代わり、example18 で使われていた Int 型と String 型の値を IO Int 型と IO String 型に変更している。IO a 型のコンテナの値は IO モナドが一方向モナドなので取り出せない。したがって、継続モナドの中で do ブロックをネストさせて実行している。

example20.hs の中核のプログラムを下に示す。

toIO :: a -> IO a
toIO x = return x

fun :: IO String
fun = do n <- (readLn::IO Int)         -- this is an IO monad block
         convert n

convert :: Int -> IO String
convert n = (`runCont` id) $ do        -- this is a Cont monad block
              str <- callCC $ \exit1 -> do    -- str has type IO String
                when (n < 10) (exit1 $ toIO (show n))
                let ns = map digitToInt (show (n `div` 2))
                n' <- callCC $ \exit2 -> do   -- n' has type IO Int
                  when ((length ns) < 3) (exit2 (toIO (length ns)))
                  when ((length ns) < 5) (exit2 $ do putStrLn "Enter a number:"
                                                     x <- (readLn::IO Int)
                                                     return x)
                  when ((length ns) < 7) $ do let ns' = map intToDigit (reverse ns)
                                              exit1 $ toIO (dropWhile (=='0') ns')
                  return (toIO (sum ns))
                return $ do num <- n'  -- this is an IO monad block
                            return $ "(ns = " ++ (show ns) ++ ") " ++ (show num)
              return $ do s <- str -- this is an IO monad block
                          return $ "Answer: " ++ s

example20.hs はコピベで動作するが、import の部分を次のように変える必要がある。

import System.IO
import Control.Monad
import System.Environment
import Data.Char
import Control.Monad.Cont

実行例は次のようになる。

Prelude> :l example20.hs
[1 of 1] Compiling Main ( example20.hs, interpreted )
Ok, modules loaded: Main.
*Main> :main
1001
Enter a number:
5
Answer: (ns = [5,0,0]) 5

管理人注:

上のプログラムがやや複雑なので、IO モナドの中に継続モナドをネストさせ、その継続モナドの中にさらにIOモナドをネストさせるプログラムを作ってみた。

Prelude Control.Monad.Cont> do { x <- runCont (return $ do getLine) id; putStrLn x}
hello
hello

読みにくいが IO モナド -> Cont モナド -> IO モナドの2重のネストなっている。最内層の getLine は IO String 型のデータを返すが、それは Cont モナドにラッピングされる。runCont でContモナド値の IO String 型のデータが取り出され、再外層の IO モナド内で実行される。example20 も大まかにはこのテクニックを使っている。

複雑にみえるが、関数の戻値が IO a や Cont r a などのモナド値になるのをイメージしていればプログラムできる。

前へ 目次 次へ
[PR]
by tnomura9 | 2013-07-24 17:50 | Haskell | Comments(0)

知的生産の技術とは何か

若いときに梅棹 忠夫 先生の『知的生産の技術』を読んで感動した。早速京大型情報カードを買い込んだり、A5版のファイリングキャビネットを買ってわくわくとした気分になっていた。自分の中にはなにかすばらしいアイディアが埋もれていて、情報カードを活用する事でそれがだんだんと形になってくるのではないかと期待したからだ。

しかし、この年になったとき、自分の中に埋もれているはずのすばらしいアイディアは一向に姿を現さなかったし、ファイリングキャビネットもいつしか姿を消していた。あの、「何かすばらしいものが生まれるに違いない。」という高揚感は、結局の所、「知的」「生産」「技術」という3つの言葉がかき立てた幻影のようなものだった。

この3つの言葉の発する魔力は、それらが、気持ちを高揚させるような価値観の概念を表しているからだ。それはある価値観を抽象的に表しているが、具体性を欠いている。いろいろな具体的な知識や技術を包含しているが、しかし、その具体例とは別のものなのだ。

「知的生産の技術」は具体的な作品が現れたときに、確かにそこに潜んでいた事がわかるが、「知的生産の技術」そのものを追い求めても雲を掴むようなものだ。

もちろん、情報をA5版のカードにまとめる事で情報に適度な粒度をあたえ、また、カード化するという事で、それらの情報の組み合わせを自由に変える事ができる。いわば、知識をコンテナ化するという「知的生産の技術」の重要性は明らかだ。管理人の失敗は、それを実際の創造に利用しなかったということなのだ。

「知的生産の技術」において、紙という媒体を利用するか、コンピュータを利用するかは些末な問題だ。自分の抱えている問題を解決するために、最適な方法を選べばよい。「知的生産」に方法論的なものが存在するとしたら、情報をどのように料理すれば、脳がそれらを処理するのに都合が良くなるかということだけだ。乱雑に散らばった本を整理するというのは、それらの本の内容を脳が楽に利用できるようにするための操作だ。

そういった意味で、「知的生産の技術」に関しては、梅棹先生の『知的生産の技術』と、川喜田 二郎 先生の『発想法』の2冊を読んでいれば十分だ。

しかし、何か「知的生産」を行いたいと考えるならば、それらの技法の前に、自分がどんな問題を解決したいと思っているのか、自分が一体何を作りたいのかということをまず明確にする必要がある。

...と、ここまで書いてきて矢も楯もたまらず上記の2書をアマゾンに注文してしまった。「知的」「生産」「技術」という呪文のなせる魔法だろう。
[PR]
by tnomura9 | 2013-07-23 07:27 | 考えるということ | Comments(1)

All About Monads 読解 17

The Continuation monad

Overview

Computation type:
 中断したり、リジュームしたりする処理

Binding strategy:
 継続のモナド値に >>= 演算子を介して関数を適用すると新しい継続のモナド値が作られる。

Useful for:
 複雑な分岐の処理や、エラー処理や、コ・ルーチンの処理に使われる。

Zero と plus:
 なし

代表的なデータ型:
 Cont r a

Motivation

(注意!)継続モナドを多用すると、読みにくく、メンテが難しいコードになる。

継続モナドを使う前に、継続渡しスタイル(CPS)のプログラムに精通している必要がある。また、このスタイルが開発しようとしているプログラムに対して最適なデザインかどうかを確認しておかなければならない。それというのも、他の言語で継続渡しスタイルが必要とされるプログラムも、Haskell の場合は使わないで済む場合が多いからだ。Haskell には遅延評価があるために、他のプログラムで継続を必要とするアルゴリズムについても、継続渡しスタイルを使わないですむことが多い。

継続は未来に行う処理を表している。それは、中間結果から最終の処理までの処理をさす。継続渡しスタイルのプログラムでは、継続は一連のネストした継続の合成からできている。その処理は最後の継続で終了する。最終の継続にはしばしは id が使われる。継続は未来に行う処理の処理を表しているから、継続を処理することで、処理の中断や、処理のスキップや、処理の途中で別の処理を挟む事などが可能になる。継続モナドとは、継続渡しスタイルをモナド構造にしたものだ。

Definition

newtype Cont r a = Cont { runCont :: ((a -> r) -> r) } -- r is the final result type of the whole computation

instance Monad (Cont r) where
    return a = Cont $ \k -> k a -- i.e. return a = \k -> k a
    (Cont c) >>= f = Cont $ \k -> c (\a -> runCont (f a) k) -- i.e. c >>= f = \k -> c (\a -> f a k)

継続モナドは継続渡しスタイルの処理を表している。Cont r a は継続渡しスタイルの処理を表している。その継続渡しスタイルには、中間結果の値の a 型の値と、その値を渡すための r 型の最終結果を導きだす継続がおさめられている。

return 関数は単に中間結果を渡す継続を作り出すだけだ。>>= 演算子は関数を継続のチェーンに加える。

説明だけでは分かりにくいので、ghci で実験してみた。

継続モナド (Cont monad) では、継続はラッピングされて、モナド値の runCont フィールドに納められている。したがって、継続を取り出すためには、runCont アクセサで取り出す必要がある。

Prelude> import Control.Monad.Cont
Prelude Control.Monad.Cont> runCont (return 2) id
Loading package transformers-0.3.0.0 ... linking ... done.
2

id の代わりに (*2) 継続を与えると中間結果の値 2 が (*2) に与えられる。

Prelude Control.Monad.Cont> runCont (return 2) (*2)
4

継続モナドの Kleisli 射は引数が一つで、戻り値が Cont r a 型の関数だ。Kliesli 射は >>= 演算値でモナド値と結合する事ができる。たとえば ¥x -> return (x * 3) は引数 x をとり Cont r Int 型モナド値を返す関数なので return 2 と >>= で合成する事ができる。

Prelude Control.Monad.Cont> runCont (return 2 >>= \x -> return (x*3)) id
6

継続モナドの Kleisli 射(関数)は >>= 演算子でカスケードに繋いでいく事ができる。その場合最初の中間値はそれに続く kliesli 射で次々に修飾されていく。

Prelude Control.Monad.Cont> runCont (return 2 >>= \x -> return (x*3) >>= \x -> return (x+1)) id
7

callCC

class (Monad m) => MonadCont m where
    callCC :: ((a -> m b) -> m a) -> m a

instance MonadCont (Cont r) where
    callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k

MonadCont クラスは callCC 関数を提供している。callCC 関数は継続モナドに継続をエスケープするメカニズム (escape continuation) を導入する。escape continuation を使えば、継続モナドの処理を中断して、直ちに最終的な戻り値を戻す事ができる。その作用は、Error モナドの throwError と catchError 関数の働きに似ている。

callCC 関数は現在の継続の環境で名前付き継続を引数にする。標準的な callCC の使い方では名前付き継続をつくるのに、ラムダ記法を利用する。そうして、この名前付き継続を、(そのスコープ内の)どの位置からでも呼び出すと、その継続の残りの処理は実行されずに直ちにその継続の処理から脱出する事ができる。継続の処理が多重ループになっていても、名前付き継続を呼び出せば、ループのネストの深さに関わらず脱出できる(大域脱出)。

callCC 関数の他にも強力な継続の処理関数があるが、扱い方が特殊になるので、ここでは説明を省略する。

callCC も ghci で実験してみる事にする。次の例は、callCC に名前付き継続 exit を与えて、exit に引数 2 を与えて呼び出しただけだ。

Prelude Control.Monad.Cont> runCont (callCC $ \exit -> do {exit 2}) id
2

次の例は名前付き継続の呼び出しで、継続の処理の中断が起きる事の確認だ。exit 2 の後の return 3 は実行されていない。

Prelude Control.Monad.Cont> runCont (callCC $ \exit -> do {exit 2; return 3}) id
2

次の例は callCC に when による条件分岐を組み合わせた例だ。こうなってくると、手続き言語の記述とあまり変わらなくなってくる。

Prelude Control.Monad.Cont> :set +m
Prelude Control.Monad.Cont> let
Prelude Control.Monad.Cont| branch n =
Prelude Control.Monad.Cont|   callCC $ \exit -> do
Prelude Control.Monad.Cont|     when (n == 2) (exit 2)
Prelude Control.Monad.Cont|     return 3
Prelude Control.Monad.Cont|
Prelude Control.Monad.Cont> runCont (branch 2) id
2
Prelude Control.Monad.Cont> runCont (branch 1) id
3

Example

example18.hs は callCC を使って複雑な条件分岐を記述した例だ。example18.hs はコピペで動作するが、import の部分を次のように変更する必要がある。動作の解読は上記の実験をやっていれば難しくはない。

import System.IO
import Control.Monad
import System.Environment
import Data.Char
import Control.Monad.Cont

実行例:

Prelude> :l example18.hs
[1 of 1] Compiling Main ( example18.hs, interpreted )
Ok, modules loaded: Main.
*Main> :main 20000
Loading package transformers-0.3.0.0 ... linking ... done.
Loading package mtl-2.1.2 ... linking ... done.
Answer: 1
*Main> :main 20002
Answer: 10001

example8.hs の中心部分は次のようになる。

{- We use the continuation monad to perform "escapes" from code blocks.
   This function implements a complicated control structure to process
   numbers:

   Input (n)       Output                       List Shown
   =========       ======                       ==========
   0-9             n                            none
   10-199          number of digits in (n/2)    digits of (n/2)
   200-19999       n                            digits of (n/2)
   20000-1999999   (n/2) backwards              none
   >= 2000000      sum of digits of (n/2)       digits of (n/2)
-}  
fun :: Int -> String
fun n = (`runCont` id) $ do
        str <- callCC $ \exit1 -> do                        -- define "exit1"
          when (n < 10) (exit1 (show n))
          let ns = map digitToInt (show (n `div` 2))
          n' <- callCC $ \exit2 -> do                       -- define "exit2"
            when ((length ns) < 3) (exit2 (length ns))
            when ((length ns) < 5) (exit2 n)
            when ((length ns) < 7) $ do let ns' = map intToDigit (reverse ns)
                                        exit1 (dropWhile (=='0') ns')  --escape 2 levels
            return $ sum ns
          return $ "(ns = " ++ (show ns) ++ ") " ++ (show n')
        return $ "Answer: " ++ str

上のプログラムで fun n = (`runCont` id) $ do ... の (`runCont` id) $ は flip runCont id $ と同じ。

Prelude Control.Monad.Cont> (`runCont` id) $ (return 2)
2
Prelude Control.Monad.Cont> flip runCont id $ (return 2)
2

callCC を使ったプログラムの解読は名前付き継続に注目すれば分かりやすい。最初の名前付き継続は exit1 だ。

        str <- callCC $ \exit1 ->

また、exit1 を値に関数適用している部分を探すと

          when (n < 10) (exit1 (show n))

なので、fn の引数が10未満のときはそのままの値を文字列にしたものを exit1 に渡す。すると str にその文字列が束縛されて、制御は最後の行の return $ "Answer: " ++ str に移るから、その文字列が "Answer:" と共に表示される。n < 10 の時の動作の例は次のようになる。

*Main Control.Monad.Cont> :main 7
Answer: 7

example18.hs の名前付き継続は他にも exit2 があるが、同じように名前付き継続が定義された場所と、exit2 に引数が与えられた場所に注目すれば動作の理解は exit1 の例のように簡単にできるので省略する。example18.hs には入れ子になった do 記法のネストから一番外へ大域脱出する例も示してある。

前へ 目次 次へ
[PR]
by tnomura9 | 2013-07-20 22:28 | Haskell | Comments(0)

Haskell/Continuation passing style 4

引き続き Haskell/Continuation passing style を解読する。

The type of callCC

普通、関数を調べるときはまず型を見て動作を推測するが、callCC の型は非常に複雑だ。

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a

そこで、最も単純な次の例で考えてみる。

callCC $ \k -> k 5

callCC の型と比較すると、変数 k の型は次のようになる。

k :: a -> Cont r b

要するに k は引数 a をとり Cont r b 型の値を返す関数になる。そこで、(\k -> k 2) という関数をcallCC の引数にして ghci でテストしてみた。

Prelude Control.Monad.Cont> runCont (callCC $ \k -> k 2) (*2)
4

これは k は継続だから、継続 (*2) に引数 2 を与えて 4 が得られるという意味だ。k は型が a -> Cont r b なので、Cont モナドの Kleilsi 射だ。したがって、>>= で他の Cont モナドの Kleisli 射と連結することができる。

Prelude Control.Monad.Cont> runCont (callCC $ \k -> (return 2 >>= (\x -> return (x + 1)) >>= k)) (*2)
6

注意しないと行けないのは k は最終の継続だから >>= の途中に記述されるとそれ以降の処理は無視されてしまう。

Prelude Control.Monad.Cont> runCont (callCC $ \k -> (return 2 >>= k >>= (\x -> return (x+1)))) (*2)
4

callCC の動作を型から推測するのは難しい。しかし、Cont a r 型がモナドであることに注目して、上に示したような例を試してみると何となく使い方が分かる。これが Cont モナドを使わずに継続渡しのプログラムを直接に記述していたら、お手上げの状態になるのではないだろうか。

The implementation of callCC

callCC の実装は次のようになる。『Continuation passing style』の本文にはそれに関する文献が紹介してあったが省略する。

callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k

Example: a complicated control structure

ここでは、『All about monads』の例示プログラムが引用されている。『All about monads』の Continuation Monads がわからずにこの文書を読む事になったのだが、『All about monads』のほうはもう一度チャレンジするつもりなのでこの部分はスキップする。

Example: exceptions

継続渡しプログラムの利用目的の1つは例外処理だ。例外処理の場合は、2つの継続が使われる。1つは処理が失敗してそれ以降の処理を中断する場合の継続で、もうひとつは処理が成功してその後の処理を継続するための継続だ。つぎの単純な例外処理のプログラムは、整数の割り算で分母が0になった場合の例外処理をするプログラムだ。

import Control.Monad.Cont

divExcpt :: Int -> Int -> (String -> Cont r Int) -> Cont r Int
divExcpt x y handler =
  callCC $ \ok -> do
    err <- callCC $ \notOk -> do
    &nsp; when (y == 0) $ notOk "Denominator 0"
    &nsp; ok $ x `div` y
    handler err

{- For example,
runCont (divExcpt 10 2 error) id&nsp; -->&nsp; 5
runCont (divExcpt 10 0 error) id&nsp; -->&nsp; *** Exception: Denominator 0
-}

実行例は次のようになる。

*Main Control.Monad.Cont> runCont (divExcpt 10 2 error) id
5
*Main Control.Monad.Cont> runCont (divExcpt 10 0 error) id
*** Exception: Denominator 0

このプログラムを読むコツは \notOk と \ok というラムダ記法の変数に継続が束縛されるということだ。もし引数 y の分母が0の時は継続 notOK に引数 "Denominator 0" が渡される。また、分母が0ではないときは継続 ok に引数 x 'div' y が渡されてその後の handler err は無視される。

ラムダ変数 notOK と ok は手続き型言語のラベルに相当すると考えても良い。ラムダ記法は一種の名前付き継続を定義すると考えられる。プログラムの途中で名前つき継続を呼び出すことで、ラベルへの goto 文と同じ働きを実現できる。

このプログラムで注意が必要なのは handler の型だ。これは Cont モナドなのだ。error 関数は Prelude で定義されており、文字列を引数にとり、エラー例外を発生させる。

*Main> error "error is defined in Prelude"
*** Exception: error is defined in Prelude

しかし、ghi で検証すると handler に束縛した error が Cont モナドであることが分かる。

*Main> runCont (error "error is a Cont monad") id
*** Exception: error is a Cont monad

例外をもっと一般的に活用できる方法としては、次の tryCont 関数がある。

tryCont :: MonadCont m => ((err -> m a) -> m a) -> (err -> m a) -> m a
tryCont c h =
  callCC $ \ok -> do
  err <- callCC $ \notOk -> do x <- c notOk; ok x
  h err

この tryCont 関数は処理とエラーハンドラーを引数に取り、処理 c に継続の引数 notOk を与えて実行する。処理 c がエラーを発生すればその中で notOK に引数が渡されて例がし処理が行われて err にエラー情報が束縛され、ok x はスキップされ、h err が実行される。エラーが発生しなければ、Cont モナドの処理が次の Kleisli 射に移り、ok x が実行されるが次の h err は実行されない。

この tryCont を利用したプログラムが、次の trythrow.hs だ。

-- file name: trythrow.hs

import Control.Monad.Cont

data SqrtException = LessThanZero deriving (Show, Eq)

tryCont :: MonadCont m => ((err -> m a) -> m a) -> (err -> m a) -> m a
tryCont c h =
  callCC $ \ok -> do
    err <- callCC $ \notOk -> do x <- c notOk; ok x
    h err

sqrtIO :: (SqrtException -> ContT r IO ()) -> ContT r IO ()
sqrtIO throw = do
  ln <- lift (putStr "Enter a number to sqrt: " >> readLn)
  when (ln < 0) (throw LessThanZero)
  lift $ print (sqrt ln)

main = runContT (tryCont sqrtIO (lift . print)) return

実行例は次のようになる。

Prelude> :l trythrow.hs
[1 of 1] Compiling Main ( trythrow.hs, interpreted )
Ok, modules loaded: Main.
*Main> :main
Enter a number to sqrt: 2
1.4142135623730951
*Main> :main
Enter a number to sqrt: -4
LessThanZero

継続渡しを理論的に考えると結構ややこしいが、要するに手続き型のループの中断や、大域脱出を関数言語で実現する方法と割り切って考えるといいかもしれない。その時に callCC の引数の関数のラムダ抽象された変数は、手続き型言語の goto 命令の飛び先のラベルに例えると結構コードを読むことができる。goto 命令は名前つき継続に引数を渡すことによって実行される。

手続き型言語でも goto 命令を頻用するのは勧められないが、実用的なプログラムを書く場合は避けられないことが多い。継続も手続き型の goto 文と同じような位置づけで考えたほうがいいかもしれない。

こうして見ると、関数型プログラミング言語といっても、手続き型のプログラミングと変わらないことができるのだということが分かる。ただ、イディオムについての知識がまだ普及していないために、特殊な用途にしか活用できないと思われているだけなのだろう。

いずれは関数型プログラミング言語でプログラムを記述するのが、普通に行われるという時代が来る気がする。

前へ 目次 次へ
[PR]
by tnomura9 | 2013-07-15 20:36 | Haskell | Comments(0)