« 2020年1月 | メイン | 2020年3月 »

2020年2月

2020年2月 6日 (木)

プログラミング初心者がHaskellのモナドに雑に手を出して大やけどする

 皆さんこんにちは。相も変わらず鳥居です。

さて、毎回恒例の「素人がプログラミングを雑に勉強しようとして大やけどをする」シリーズをやっていきたいと思います(そんなに恒例になってないかorz)

早速ですが、皆さんは「モナド」という言葉は聞いたことがあるでしょうか?

ぶっちゃけ筆者が「モナド」という言葉を初めて目にしたのは、persona3というゲームの「深層モナド」という隠しダンジョンの名前からでして…って、そんなことはどうでもいいか。

恐らくHaskellを勉強している、あるいは業務などで使用している方なら知っているのみならずゴリゴリに使っているのがモナドだと思われます。また、そうでなくともプログラミングを勉強している方なら一度ならず目にしているのではないでしょうか?

 さてそんなモナドですが、ネットで情報を収集していると、

・モナドとは計算を表現する構造である。

・returnメソッドと>>=演算子が定義されている。

・Haskellで入出力を行うためにはIOモナドが必須

・素人は今すぐモナドを深く理解しようとするのをやめろ

といった説明がなされています。…間違っても私が手を出すべきものではないですね…orz

…とりあえず、すこーしずつモナドに手を突っ込んでは引っ込めることをやっていくことにします。

まず具体例としてwikipediaからの引用を見てみることにします.

https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%8A%E3%83%89_(%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0)

data Maybe t = Just t | Nothing

上がMaybeモナドの宣言となっています。先頭にdataとついているということは代数的データ型であるということですね。…多分。

使用例を見てみると、

add :: Maybe Int -> Maybe Int -> Maybe Int

add mx my =

    mx >>=(\x ->

     my >>=(\y ->

       return (x + y)))

見たいに使うようです。…早速わけが分かりません。

とりあえず、このadd関数は、

・引数に Maybe Int 型を二つとり

・返り値として Maybe Int型の値を返す

関数でしょうか…?うーん分からん。

などと泣き言をいうのはやめてもうちょい観察してみることにします。

・>>=演算子が存在する。

・解説を見てみると、mxとmyがNothing ではない場合に限りこの関数は成功する。

・さらに解説を見てみると、

 return :: a  -> Maybe a

 return x =Just x

というメソッドがMaybeモナドには実装されている。

といったことがわかります。

おや?一番最初の方で書いた、

・returnメソッドと>>=演算子が定義されている。

というモナドの原則が一番目と三番目の観察結果から見て取れます。ふむ、ちょこっとだけ考える糸口が見えてきました。

returnメソッドから見ていきます。

return :: a -> Maybe a

これがreturnメソッドの宣言内容です。aという型を引数にとり、Maybe  aという型にして返すメソッドらしいですね

return x = Just x;

ここでいうJust とはMaybe型を代数的データ型と見たときのコンストラクタに値しそうです。よってこのメソッドは、型aのxという値をJust xという型Maybe aの値にして返す関数となるようです。

次に>>=演算子についてみてみる…その前にHaskellの演算子について少し触れておきましょうか。

Haskellでは、演算子も関数の一つとしてみなされるようです。例えば、

1 + 2

という演算(もちろん答えは3になりますよね?)があった時、

(+) 1 2

という風に、関数っぽく書けるようです。というよりは、1+2の方が(+) 1 2の別名であると言ったほうが正しいでしょうか。

それを踏まえて>>=の宣言も見てみることにします。

(>>=)::Maybe a -> (a -> Maybe b)-> Maybe b

見てもらえばわかる通り(…大丈夫ですよね?)、(>>=)演算子はMaybe型においては

「Maybe a型の値と、「a型の値を引数にとり、Maybe b型の値を返す関数」を引数にとり、Maybe b型の関数を返す」関数であることがわかります。…頭がこんがらがってきた。

具体的な内容は、

NOthing >>= _ =Nothing

(Just x) >>= f =f x

となっています。関数型言語特有のパターンマッチ記法が出てきていますが、それはこの際無視(!)するとして、どうやらこの関数は、

・NothingというMaybe a型の値が与えられた場合にはそのままNothingを返す。(…実際には_というワイルドカードで「a型の値を引数にとり、Maybe b型の値を返す関数」を…難しくなりそうなのでこれ以上は書きません)

・Just xというMaybe a型の値と、fという「a型の値を引数にとり、Maybe b型の値を返す」関数が与えられた場合、xにfを適用した値(Maybe b型の値)が返される

演算子(関数)となっているようです。…疲れた。

さらにその上で先ほどのadd関数を見てみると

add mx my =

    mx >>=(\x ->//ここでmxというMaybe Int型の値と\x以降の「Int型の値を引数にとり、Maybe Int型の値を返す関数」を引数にとり、

     my >>=(\y ->//ここでmyというMaybe Int型の値と\y以降の「Int型の値を引数にとり、Maybe Int型の値を返す関数」を引数にとり、

       return (x + y)))//最終的にxとyを足したものをMaybe Int型にして返す

関数となっている…もう無理。

-------------------------------------------------------------------------------------------------

今回のまとめとしましては、

・素人がモナドを深く理解しようとすると大やけどする

になるでしょうか…ぐふっ(続くかもしれない)。

2020年2月 5日 (水)

ABC153-E Crested Ibis vs Monster 個数制限なしナップサック問題について雑にまとめる

 どうもこんにちは。毎度おなじみ鳥居です。

 今回も例によって例のごとく、プログラミング初心者がプログラミング手法について雑にまとめていこうと思います。駄文雑文ご容赦くだ(ry

https://atcoder.jp/contests/abc153/tasks/abc153_e

 さて、いきなりですがトキさんがモンスターと戦っています。

 モンスターのヒットポイントと攻撃の種類が与えられ、それぞれの攻撃方法について攻撃力と魔力の値が設けられています(同じ攻撃方法を何度も選んでよい)。トキさんがモンスターを倒すまでに必要な魔力の最小値はいくらになるでしょうか?という問題です。

 そして結論から言えばこの問題は「個数制限なしナップサック問題」という有名問題をアレンジした問題だそうです。

この「個数制限なしナップサック問題」について簡単に説明すると、

「入れることができる重さの最大値が定まったナップサックに、重さと価値がそれぞれ決められている荷物を、同じものを二つ以上入れてもよいという条件で入れたときに価値の最大値を求めよ」

という問題です。この場合ですと、重さの最大値をモンスターのヒットポイント、荷物の重さと価値をそれぞれトキさんの攻撃力と魔力に対応させればよさそうですね。

 さあ、この問題はどう解くべきでしょうか。

 以前動的計画法について(雑に)まとめたエントリで、各々の荷物を入れるか入れないかで分けて解こうとすると計算量がとんでもないことになると説明しました。さらに今回は個々の入れれる荷物の量も無制限ですので、その量も鑑みるとさらに計算量が増えることになりそうです。

 となると、動的計画法の出番になる予感がしてきます。具体的にはそれぞれの攻撃方法について、ヒットポイントの値を一つずつ増やしながら攻撃回数と攻撃力の数を掛けた値までdpテーブルを埋める方法が考えられそうです。

 …なんですが、この方法でもまだ計算量が多くなりそうです。攻撃回数まで考えると三重ループになってしまいますからね…orz

 どうしましょう。どうしましょうか。お手上げです。

 こんなときは私たち競プロerにとってのバイブル、通称蟻本の助けを借りましょうか。

https://www.amazon.co.jp/dp/B00CY9256C/ref=dp-kindle-redirect?_encoding=UTF8&btkr=1

 この本の中で個数制限なしナップサック問題はこんな風に解けばよいと書いてあります(私自身の読解ミスがあるかもしれません。また、説明文中のiはi種類目までの荷物の選び方、jは重さの最大値、w[i]はi番目の荷物の重さを表していると思ってください)

「dp[i+1][j](iの種類を一つ増やしたときのdpテーブルの値)の計算においてk(>=1)個選ぶ場合は、dp[i+1][j-w[i]](すでに求めてある、iの種類を一つ増やして重さからw[i]を引いたときの値)の計算においてk-1個選んだ場合と同様であるため、dp[i+1][j]の漸化式におけるk>=1の部分の計算はすでにdp[i+1][j-w[i]]の計算時に行っている。よってその値に価値を足したものと、今現在の値を見比べて適している数でdpテーブルを埋めればよい」

…はい。自分で書いててわけが分からなくなりましたorz。まだまだ勉強が足りなさそうです(:_;)

とにかく(投げた)、このような計算方法でdpテーブルを埋め最終的に求められている解を出せばよさそうです。

 いくつか注意しなければならないのが、ABC153-Eの問題では「モンスターの体力を決めたときの魔力の最小値」を求めるべき(魔力の値を決めたときのモンスターのヒットポイントの最大値を求めると計算量がオーバーしてしまう)ことと、答えはdp[H]<=dp[i]<dp[H+maxA_i]の間の最小値であること(dp[H]をmaxA_iまで更新する必要がある)でしょうかね。うん、やっぱり訳が分からなくなって(ry

以上で私の雑な説明は終わりです。ぶっちゃけ他の方の簡潔かつ丁寧な説明記事をご覧になられたほうがいいですね…orz

http://drken1215.hatenablog.com/entry/2020/01/26/225000

上にけんちょんさんという競プロ界隈では知らない人はいないであろうすごいお方が書いた今回の問題の解説のリンクを貼ったので、もしよろしければこちらを参照してください。(私の書いたものよりずっと分かりやすい説明が載ってますので…)

2020年2月 4日 (火)

素人が代数的データ型について雑に考えてみる

 どうも、鳥居です。今回はHaskellやOcamlなどの関数型言語に特有の代数的データ型について考えてみたいと思います。例によって超初心者が書き下した雑文なので多々到らない部分があると思いますがご了承ください(;'∀')

 https://ja.wikipedia.org/wiki/代数的データ型

 さて、この代数的データ型ですがwikipediaではこのように書いてあります。

「代数的データ型の値(データ)の感覚的な説明としては、引数で与えられた他のデータ型の値を、コンストラクタで包んだようなもの、である。」

…はて、何のことでしょうか…(@_@)

コンストラクタってあれですよね。Javaとかでクラスを作るときにフィールドの値を初期化するときとかに使うあれですよね。それでデータ型の値を包むっていうのは…どういう意味だ(+o+)

とりあえずHaskellで代数的データ型を宣言するときにどう書くのか見てみますか。

data Node = Leaf Integer | Branch Node Node

…うーん、分からん。

などと泣き言をのたまうのはやめてよくよくどういう意味なのか考えてみるとどうやら、

・まずある複数の型を表す抽象的で大きな型がある

・その型に含まれる型をその大きな型に代入(?)することで抽象的だったその大きな型の具体的な型が決定する

…感じみたいです(*_*;

うん、素人が雑に手を出すべきやつではなかったorz

まあ、もう少しだけ考えてみることにしますか。

https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0-OCaml-%E3%80%9C%E9%96%A2%E6%95%B0%E5%9E%8B%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%AE%E5%9F%BA%E7%A4%8E%E3%81%8B%E3%82%89GUI%E6%A7%8B%E7%AF%89%E3%81%BE%E3%81%A7%E3%80%9C-%E4%BA%94%E5%8D%81%E5%B5%90%E6%B7%B3-ebook/dp/B00QRPI1AS

上の書籍で記されているヴァリアント型(これも代数的データ型の一つのようです)の例を参考にしてひも解いてみたいと思います。

この本では代数的データ型を、

「作り方に複数の方法があるようなデータ(型)」

と定義しているようです。

例えば、「図形」という抽象的な型があるとします。

図形といえば、

・点

・円

・長方形

・正方形

などの種類がありますよね?

これらをそれぞれ別個の型として扱うよりも、まず大きく

図形

と定義してから

図形の点

図形の円

図形の長方形

図形の正方形

とまとめたほうが、なんていうか、気持ちいい(?)ですよね?(何を言ってるんでしょう私は…)

そういったときに役立つのが代数的データ型となります。

Ocamlでの宣言方法を例にとると、

type figure=(*figure型の宣言*)

|Point(*点*)

|Circle of int(*円*)

|Rectangle of int * int(*長方形*)

|Square of int ;;(*正方形*)

といった感じに宣言します。具体的に値を生成するときは、

let c = Circle 3;;

と記述します。こうすることで

val c:figure(*cはfigure型*) = Circle (*cはCircle(円)である*) 3;;

といった感じで構築されます。…難しい('Д')

ここで先ほどのwikipediaの説明に戻ってみます。

「代数的データ型の値(データ)の感覚的な説明としては、引数で与えられた他のデータ型の値を、コンストラクタで包んだようなもの、である。」

上の例だと、「Circle」がどうやらコンストラクタで、「figure」が代数的データ型に相当しそうです。

じゃあ、3は…?

すみません。説明不足でしたね(:_;)

コンストラクタを定義したときの

of int

of int * int

は、大きさを決めるときに必要なものでした。円だと、

・int型の値一個を半径として引数にとって

・半径×半径×3.14

が大きさとして返されればいいですし、長方形だと

・int型の値二つを引数にとって

・縦×横

を大きさと返せばよいわけです。(本当に申し訳ございません。ここらへんは後で文章を推敲しますorz)

…ということは? そうですね。「引数で与えられた他のデータ型」が上での「3」に相当しそうです。(本当に回りくどくなってしまった)

さすがにこれ以上長ったらしく書くと収拾がつかなくなりそうなので今日はこの辺にしておきます。お見苦しい文章をお見せしてしまい本当にすみませんでした。機会があればもう少しだけ掘り下げてみたいと思います。

2020年2月 3日 (月)

三王岩を見に行ってきました(^^)/

Dscf0035

Dscf0036

Dscf0029

小さいころから何度か見てきましたが改めて見るとすごい迫力ですね(;'∀')

皆さんも機会があればぜひ田老に見に来てください(*^_^*)

Dscf0038

余談ですが3.11の津波は17mの高さまで来たんですね…(;・∀・)(写真の線の一番上のところまで)

自然の脅威ってすごい。

最後に何枚か写真を挙げておきます(@_@)

Dscf0030

Dscf0034

Dscf0020

曇りだったのが若干悔やまれますがそれでもなかなか良い風景でした

アクセスランキング

Powered by Six Apart