はてなブックマーク

この記事はlotzさんの「動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜」という記事を読んで、自分の問題に対しても応用できないかと考えた結果をまとめたものです。 先に元の記事を読んでから以下の内容を読んで頂けるとスムーズかと思われます。 最長交易路とは 皆様は『カタン』というゲームをご存知でしょうか？ カタンは複数のプレイヤーが無人島を開拓して、最も繁栄させることができたプレイヤーが勝利するというボードゲームです。 このゲームには「最長交易路」というルールがあり、最も長い交易路を作ったプレイヤーに追加の得点が入ることになっています。 このゲームにおける交易路はグラフ理論の言葉を借りると無向多重グラフとみなすことができます。 そして、最長交易路を探すということは、無向多重グラフの中で最長の**小道（trail）**を探すことになります。 ここでは、ある頂点からある頂点

「javascriptで難読fizzbuzz」っていうお題で書き始めました。 rnという関数でChurch数をjavascriptの整数に変換していますが、これは結果の表示用であって計算は全てChurch数のまま行ってます。 実行時の効率は考えてないので、結果が表示されるまで数秒かかります。 const z=f=>(x=>f(y=>x(x)(y)))(x=>f(y=>x(x)(y))) //Zコンビネーター const id=x=>x //恒等関数 const sc=n=>f=>x=>f(n(f)(x)) //succ const pr=n=>f=>x=>n(g=>h=>h(g(f)))(tr(x))(id) //pred const mn=m=>n=>n(pr)(m) //引き算 const pl=m=>n=>n(sc)(m) //足し算 const ml=m=>n=>n(pl(m))(

GHCi> import Data.Function(flip) GHCi> let (>.>) = flip (.) GHCi> :t (>.>) = flip (.) (>.>) :: (a -> b) -> (b -> c) -> (a -> c) GHCi> let showSqrt = sqrt >.> show GHCi> showSqrt 2 "1.4142135623730951" この演算子は、(.)演算子の引数の順番を逆にしただけです。 さて、この演算子について以下の3つの式が常に成り立ちます（重要） id >.> f ≡ f （idの左単位性） f >.> id ≡ f （idの右単位性） (f >.> g) >.> h ≡ f >.> (g >.> h) （結合則） 型コンストラクタ付きの関数の結合 世の中には戻り値が型コンストラクタに包まれていても普通の関数と同じ

Functor（関手）の話です。 HaskellのFunctorクラスはHask圏からHask圏への関手しか表現できません。 そこで、Hask圏以外の圏についても使える関手のクラスを書いてみました。 よろしくね　(*´σｰ｀)ｴﾍﾍ #基本的な用語と、HaskellのFunctorクラス 別のところにまとめました この章に書こうとしていた、「基本的な用語の確認とHaskellのFunctorクラス」についての内容は、別の記事にまとめさせて貰いました。 内容としては、「HaskellのFunctorクラスはHask圏からHask圏への関手しか表現できません。」という文章の説明なので、それを読んで「そらそうだろ」って感じなら読み飛ばして次の章を読んで頂いて大丈夫です。 #とびだせ！Hask圏 HaskellのFunctorは、Hask圏からHask圏への関手を表現しています。 しかし、Hask

タイトルは、[Haskell] FunctorクラスはHask圏からHask圏への関手となっていますが、 もっと正確には、[Haskell] FunctorクラスはHask圏からHask圏の部分圏への関手のほうが、より適切かもしれません。 もともとこの記事はHaskellアドベントカレンダー(その3)の、12/14に登録した「とびだせ！Hask圏」という記事の前半部分として書いていたものです。 。 ただ、その記事がクソ長くなってしまいそうだったので、前半を分離して一つの記事にしたのがこの記事になります。 基本的な用語 圏とは 圏の公理を書こうかと思ったんですが、結構面倒くさいので省略します。 忘れちゃダメなポイントは、 すべての対象に恒等射が存在する。 射の合成は結合則を満たす。 という点です。 Hask圏とは 対象はHaskellの、カインドが*である型 射はHaskellの関数 射の始

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article?