背景 動的計画法を実行する際、計算した部分問題の解をテーブルに書き込んでいくわけだが、問題によっては、テーブルの全体を最後まで持っておく必要がないこともある。 例として、2つの文字列のレーベンシュタイン距離を求める問題を考える。二つの文字列の…

多くの場合、gitのマージコンフリクトの解決は簡単な作業である。これに生活の約1%を費やしているのだが、どうも適切な道具がないせいで効率が悪い気がしていた。たとえばvimdiffは、二つのファイルを比較するのであればとても優秀なのだが、マージコンフリ…

最近のvimは、:editや:splitなどのコマンドでディレクトリを開こうとするとnetrwを起動する。しかし、私がこれをやるのは九割九分、tab補完の後すぐにEnterを叩いたものの補完されたものが予想と違った場合で、ディレクトリを開くのは邪魔な挙動でしかないの…

今年もICFP Programming Contestに参加していた。今回は「Japanese Curry.」というチームで、メンバーはA氏とJ氏と私の三人だった。今回の問題はテトリス風のゲームをプレイするAIを作るというもの。以下のような特徴がある。 ゲーム盤が六角形の敷き詰めで…

これを書いている時点でAtCoderのHaskell処理系はGHC 7.4であり、これはプログラムに対してデフォルトで8MBのスタック制限を課す。したがって、深さ数十万の再帰を普通に書くと容易にスタック溢れによるREを起こす。このスタック制限値はコンパイル時または…

ICFPコンテストに参加していた。今年はLightning Divisionのみで、一人チームでの参加。Lightning Divisionの課題は、あるゲーム*1をプレイするAIを書くというもので、最初はよくある問題のように思ったのだが、結果的にはかなり楽しめた。というのも、提出…

観測にノイズが乗っても対処できる二分探索が意外と簡単に書けることが分かったのでメモ。 問題 (n-1)個の整数からなる列がある。そのうち左からi個は(-1)であり、それ以外は1である。 n=6, i=3の例 -1 -1 -1 1 1クエリを繰り返すことでiを求めたい。各クエ…

IOモナド上で動作するcall/ccを実装できることが分かったので書いておく。ただし実用に耐えるものではない。これを使うとたとえばこういうコードを書くことができる。 import Control.Applicative import Control.Monad import Data.IORef import System.IO.…

これはHaskell Advent Calendar 2013の(3+π)日目の記事です。(3 + pi)や(quot 7 8)のような単純な定数式は、ghc -Oが行なう定数畳み込みによってコンパイル時に計算される。uncurry (*) (3, max 5 2)のようなやや複雑な式も、インライン展開してから定数畳み…

変な議論してたら教えてください！ 命題0 を集合、を圏、を忘却関手、を自由関手とすると、以下が成り立つ。 証明 米田の補題からなので、を示せば良い。はの左随伴だから、単位と余単位が存在して以下が成り立つ。 以下で具体的に同型射を構成する。写像と…

メモ。Haskell Reportによれば、(do a)という式の意味は(a)と同じなので、aがモナドな型を持っている必要はない。これを利用して、括弧を減らすためだけにdoを使うことができる。 import Data.Complex import Data.Monoid import Data.Text.Lazy.Builder imp…

Haskellでのデバッグといえばprintfデバッグなのではないかと思う。printfデバッグは大抵の場合うまくいくが、多相的な関数を書いているときは不便なことがある。表示したい値を文字列にする手段がない場合だ。 import Debug.Trace import Data.List mysort …

通常のレコード型は一旦定義したらフィールドを追加したりはできないが、Template Haskellを使えば似たようなことができるのに気付いたので書いてみた。次のように使う。 {-# LANGUAGE TemplateHaskell, TypeFamilies, DeriveDataTypeable #-} import OpenPr…

Haskell vs F# - Life Goes Onが気になったのでやってみた。手元にF#の実行環境がないので、元のコードを2倍高速化することを目標にしてみる。環境はLinux x64, GHC 7.0.4.最初のコード。 import Data.Array.Unboxed data Node = Node { df :: Double, branc…

Haskellコードを書いていて、インデントを揃えるのが面倒だとか、インデントが揃っているか判別しにくいということがあるかもしれない。以前は私にもよくあったのだが、二つの簡単な指針に従うことに決めてからこの種の問題に悩まされることはなくなった。の…

Haskellはオブジェクト指向言語ではないが、コードを書く上でオブジェクト指向の考え方を利用するのが便利なこともあると思うので紹介する。 オブジェクト指向とは何か オブジェクト指向という言葉に共通定義がないのは共通認識だと思う。気をつけないと議論…

iterateeって良く聞くけど何が良いの、と思ってるHaskellユーザのためのメモ。iterateeについては既に日本語の紹介が複数あるが、この記事では実装の詳細に立ち入らず、何が嬉しくてあんな奇妙なインタフェースになっているかについてだけ説明する。具体的な…

今年もICFP Programming Contestに参加していた。今回は職場のチームで出てみた。といっても開催日時が悪かったせいでたった二人のチームになってしまったが。相棒のpacakはHaskellerで、本業はISPの経営者らしい。開始前、サーバが欲しいなあと呟いたら、メ…

(追記(2011-07-30): '記号を含むprofファイルの解析に失敗するバグを修正したものをGitHub - mkotha/viewprof: A viewer of GHC .prof files with curses interfaceに上げた) +RTS -pで出力される.profファイルには呼び出しグラフが含まれていて大変役に立つ…

なにこれ Haskellは素敵な言語だと思うが、デフォルトが遅延評価であることに起因する欠点のせいで魅力を50%くらい損なっているように見える。具体的にはサンク構築/評価のオーバーヘッドとメモリリークで、特にメモリリークの実害は大きい。ならば必要な所…

eagerな言語ではfoldrはリストの長さに比例するスタックを消費する。GHCでも(+)のような正格な関数で畳み込もうとすれば同様にO(n)の振る舞いになる。 {-# OPTIONS_GHC -O0 #-} import Data.List(foldl') main = do n <- readLn print $ foldr (+) 0 [1..n] …

http://haskell.g.hatena.ne.jp/route150/20101224/1293122299を見て気になったので、エラトステネスの篩を書いてみた。n以下の素数の和を表示する。 import Control.Monad import Data.Array.ST import Data.Array.Unboxed import Data.Array.Base(unsafeRe…

強剣師の探索をm100についても行なったので結果を書いておく。注意: これは(おそらく)解ではないし、解の良い近似になっている保証もない。

Grapefruitが気になってしょうがないので、おもちゃの電卓を書いてみた。GrapefruitはFRPライブラリの一つで、定期的なポーリングを必要としないpush型の設計でありながら、push型FRPにありがちな問題をいくつか解消しているのが売りらしい。 ループのある回…

Cプリプロセッサがマクロの再帰的な展開を許さないのは良く知られていると思う。 #define A() [B()] #define B() {A()} A() /* [{A()}] に展開される */ つまり、あるマクロの展開中に、それと同名のトークンが出現した場合、展開を行わない。特定のマクロに…

この変換規則は以下のコードで生成したもの。これをgen.scmなどと名付けて、uim-sh $(pwd)/gen.scm | fold -sのように実行する。このコードの最後のprintの呼び出しを削除すればそのまま.uimとしても使えるが、アプリ起動のたびに走るコードとしては重すぎる…

(追記:2010-09-19)以下の手順は、uim-skkだと辞書の変更を要し、uim-anthyだと正常に動作しないことが分かりました。要するにこのままでは役に立ちません。二年以上前のコードなので細かい注意事項を忘れていました。いずれ修正版の記事をあげるかもしれませ…

uimでのローマ字入力は、MS-IMEと違って、 無駄な子音が消される(例: "sk" -> "k") 子音連続が、即座に「っ」になる(例: "tt" -> "っt") ため、語末に全角の草を生やしたり、くぁｗせｄｒｆｔｇｙふじこｌｐを入力するのが面倒だ。この点をMS-IME風の動作に…

プリプロセッサメタプログラミングの話。Cプリプロセッサ上で値の列を表現するためのデータ構造の一つとしてsequenceというのがある(Boost.Preprocessorの用語)。 他の言語でいうリストや配列に似たもので、以下のような形をとる。 (0)(1)(2)(3) /* 0から3ま…

Haskellでフィボナッチ数を計算するコードとして、次のものが有名だ。 fib :: [Integer] fib = 1 : 1 : zipWith (+) fib (tail fib) これのn番目の要素を取得するコードがO(n^2)よりも遅いということを指摘した記事があった。 Haskellの「fib = 1:1:zipWith …