先日 Gotanda.hs #1 @HERP というイベントがあって、そこでRecursion Schemesで考える並べ替えアルゴリズムというタイトルでA Duality of Sortsという論文の話をLTしたんですが、この記事ではそこで話せなかった論文の後半で解説されている挿入ソートと選択ソートの双対性について書いていきたいと思っています。 ソートアルゴリズムの復習 まずは主役の二人である挿入ソートと選択ソートについて見ていきましょう。 挿入ソートは与えられたリストの先頭から要素を取り出し、これまでに構築したソート済みのリストに挿入していくという処理を繰り返すことでソートを実現するアルゴリズムです。 出典: Insertion sort - Wikipedia これをHaskellで実装すると以下のようになります。 insertSort :: [Int] -> [Int] inser

Graphvizはオープンソースのグラフ描画ソフトです。dot言語というグラフ構造を記述する言語によって書かれたグラフを綺麗に描画してくれます。Graphvizの良いところの一つはdot言語でグラフ構造さえ書けばノードやエッジをどのように配置するかは勝手に決めてくれるところでしょう。この機能があるおかげでグラフの管理や自動生成などが簡単に実現できます。 しかしグラフを描きたいと思っただけなのに新しい言語を覚えるのは大変です。加えてdot言語には変数や関数など抽象化をサポートする機能が乏しく複雑なグラフを描こうとするとコピペが大量に発生して記述が冗長になることもあります。そこでgraphvizというライブラリを使えばHaskellのEDSLとしてグラフ構造を記述することが可能になり、直接Graphvizを通してグラフ画像を生成することができます。必要ならdot言語を生成することも可能です。ち

仰々しいタイトルになってしまいましたが、内容はこんな便利な学習モデルの書き方が出来るよって紹介です。A Purely Functional Typed Approach to Trainable Models (Part 1)で語られているコードをベースにして説明していきたいと思っています。 この記事で紹介する内容は新しい機械学習の理論でもなければ明日から役に立つデータサイエンティストの知識でもありません。線形回帰やニューラルネットワークといった既存の学習理論を表題にもあるような微分可能プログラミング（Differentiable Programming）と純粋関数型言語を使って統一的に記述してみようというものです。こういった抽象化は理論に対する理解を深め、時に新しい構造の発見につながるでしょう。 本編に入る前に微分可能プログラミングという概念について簡単に触れておきます。 まず可微分プロ

class Functor m => Monad m where return :: a -> m a (>>=) :: (a -> m b) -> m a -> m b join :: m (m a) -> m a join = (>>= id) k >>= m = join $ fmap k m extract は return と、extend は >>= と、duplicate は join と、それぞれなんとなく反対になってるような気がしますよね？（m と w も上下反対の対応がありますねｗ） コモナドの感覚を掴むために具体的な実装を見てみましょう。 -- | List Zipper data Z a = Z [a] a [a] left, right :: Z a -> Z a left (Z (l:ls) c rs) = Z ls l (c:rs) right (Z ls c

LambdaConfがツイートにて関数型プログラミングのレベル分けを発表していました。今後LambdaConfから発信される発表にはこのレベルが表記され, 自分のレベルにあったコンテンツが探しやすくなるようです。このレベル分けはプログラマの優劣を付けるようなものではなく, 広く深い関数型プログラミングの世界で自分が今どのレベルにいるのかを適切に理解し次にどこに向かうべきなのかを知るのにたいへん役に立つものだと思います。 表を眺めてみると関数型プログラミングというよりかはHaskellのレベル分けのような印象も受けますが、広く知られるべきだと思ったので翻訳してみました。僕が未熟でトンチンカンな訳をしている箇所もあると思うので、何か見つけた場合は遠慮なくコメントや編集リクエストをお願いします LambdaConf Ladder of Functional Programming (LOFP)

最近の趣味は「Haskellはいいぞ」と呟くかTwitter Search: Haskellを巡回して を押して回ることです 毎日巡回しているとHaskellに入門しようとするも細かいところに引っかかって前に進めないでいる人をちらほら見かけます。今回はそんな見回りの知見を活かしてHaskell初心者が躓きやすいポイントをまとめてみたいと思います。 1. 入門書は何がいいの？ それはもうすごいH本一択でしょう！…と言いたいところですが時々不満の声を聞くこともあります。確かにすごいH本こと『すごいHaskellたのしく学ぼう!』は世界一わかりやすいHaskell入門書であることは間違いないと思いますが、逆に内容が平易すぎるため記述が冗長だと感じたり読み終わっても何か自分で作れるようになった気がしなかったりするかもしれません。なので僕は「プログラミングも初心者でHaskellから入門してみたい」

トロピカル半環と呼ばれる代数構造上のトロピカル行列を利用すると動的計画法を使ってグラフの最短経路の距離を計算するという問題が単純な行列積で解けてしまうらしい。そんな噂12を聞きつけて我々はその謎を解き明かすべく南国（トロピカル）の奥地へと向かった。 トロピカルな世界に行くためにはまずは代数を知る必要がある。要するに群・環・体の話だ。しかしこの記事の目的は代数学入門ではないので詳しい話は他の記事3に譲るとし、さっそく半環という概念を導入する。それは 半環は以下の性質を満たす二つの二項演算、即ち加法（和）"$+$" と乗法（積）"$\cdot$" とを備えた集合$R$を言う $(R, +)$ は単位元 $0$ を持つ可換モノイドを成す: $(a + b) + c = a + (b + c)$ $0 + a = a + 0 = a$ $a + b = b + a$ $(R, \cdot)$ は単