Haskellでメモ化を行うもう一つの方法 - 純粋関数型雑記帳
はじめに Haskell で動的計画法を書くための3つの方針 - tosの日記 これを読んで、私もちょっと前にHaskellでメモ化をやる方法を考えていたことを思い出したので、書いてみることにします。 Haskellでのメモ化は、私のかなり昔の駄文(リアルにびっくりするほど駄文なのでご注意。メモ化の綴りも間違ってます)や、このあたりに日本語の文章があります。 これらのページでのメモ化実現方針は、1. 計算済み値を保持するテーブルをMapなどを用いて用意する 2. そのテーブルを副作用を用いて更新する、というものになっています。なるほど、これは手続き型言語との対比でとても直接的な実装です。しかし、テーブルを更新するために関数全体がモナドになってしまったりして、あまり使い勝手が良くなさそうです。モナドであることを悟らせないために、演算子をモナド化したり、あるいはモナドじゃなくするためにunsa
Boost.勉強会 #4 で発表してきました - 純粋関数型雑記帳
Boost.勉強会 #4で発表してきました。ICFP Programming Contest 2010 での Discriminating Hacker's 言語の件から、 C++をDISるというテーマで話す機会を頂いたので、せっかくなので、発表させていただくことにしました。 C++コミュニティーの中心でC++をDISる View more presentations from tanakh C++プログラマ、所謂闇の軍団の集う中でこのような発表をするのは、まさに飛んで火に入る夏の虫というやつで、戦々恐々としていたのですが、思惑とは逆に、全然DISれていないと私がDISられるというような結果となりました。 Haskellerの目線から、C++の気に入らない点を、主に型の話をメインに展開していったのですが、おおよそのC++erにとってはあまり賛否両論とは言えなかったようですね。なんでしょうか
関数型！侵略ノススメ☆ - 純粋関数型雑記帳
（この記事は Functional Ikamusume Advent Calendar jp 2010 の為に書かれました） 侵略！侵略！侵略！侵略！侵略！侵略！イカ娘！ 再帰しなイカ？ main = putStrLn $ f 6 where f 0 = "イカ娘！" f n = "侵略！" ++ f (n-1) 古風に再帰しなイカ？ main = putStrLn $ f 6 where f 0 = "イカ娘！" f (n+1) = "侵略！" ++ f n 左派じゃなイカ？ main = putStrLn $ foldl (\a _ -> "侵略！"++a) "イカ娘！" [1..6] 右派じゃなイカ？ main = putStrLn $ foldr (\_ a -> "侵略！"++a) "イカ娘！" [1..6] 右派に見せかけた左派じゃないか？ main = putStrLn $
Haskellのエラー処理とMonadCatchIOの落とし穴 - 純粋関数型雑記帳
（この記事はHaskell Advent Calendar jp 2010のために書かれました） Haskellではエラー処理に例外が用いられます（MaybeモナドやErrorモナドも用いられますが、ここでは例外に焦点をあてます）。 例外インターフェースの話 Haskellにも、例外を扱うためにtry, catch, finallyなどが用意されています。他の多くの言語ではこれらは構文として用意されますが、HaskellではIOモナドを引数にとる関数になっています。 try :: Exception e => IO a -> IO (Either e a) catch :: Exception e => IO a -> (e -> IO a) -> IO a finally :: IO a -> IO b -> IO a tryはIOアクションを引数にとり、それを実行した結果が正常に値を返
2005-12-30
C言語にコピーGCを実装できるような気が突然したので、 家に帰って早速作ってみた。 C言語から使えるGCとしてはBohemGCが有名であるが、 あれはmark-and-sweepだったはずなので、 あんまりパフォーマンスはよくないと思われる。 (mark-and-sweepはストレージに比例する時間、 コピーGCは生きているデータに比例する時間がかかるゆえ) なお、今回の実装は原理的にはジェネレーショナルにするのもたやすいので、 潜在的パフォーマンスはもっと高いと言える。 今回の実装を説明する。 int with_gc(int (*f)(),int heap_size=1024*1024); void *gc_malloc(int size); void force_collect();with_gc() は後述。 gc_malloc() はメモリを確保する関数。 確保したメモリは参照が外
2004-10-02
最近C++を使う時間が長いのでががーっと C++批判文章を書き上げてみる…。 (注：以下の文章において、C言語とはC/C++をさすものとお考えください) gotoは今から30年以上も前のダイクストラ先生による撲滅運動の 甲斐もあってかどうなのか、今日では良くないものの代名詞のように なっている。良くないということの主な理由はプログラムの流れが 見えにくくなる、等のようなのだが、実際のところどの程度のものかは よく分からない。C言語において、例えばループ構文を使わずにすべてを gotoでまかなおうとするとこれはほとんど自明に、確かに大変である。 例えばfor文なら、 for (A;B;C) body というものは、これを形式的に A _continue_for: if (B) goto _break_for; C goto _continue_for; _break_for:; このように変
GCJテンプレート - 純粋関数型雑記帳
前回日記を書いたときから一回も練習をしていないことに気づいた。 もうすぐそこに迫ってきているというのに。 テキサスに行ったときは メダルを持ち帰ってきます、などと臆面もなく言っていたが、 今回はとてもじゃないが何も期待できない。 こんなに何もせずに勝てるわけないじゃない。 それはそれとして。 Round2のときにデュアルコアが使えてれば後一問通ったのに、と思って Round3のときに準備したテンプレートでも公開してみることにする。 Round3が終わったときには、やっぱりプログラムはオーダーだ、 とか思って東京Local大会には持っていかなかったのだが、 計算機の気まぐれで通るという綱渡りになってしまったので、 Finalにはやっぱり持っていこうと思う。 あまり大きなテンプレートはバグが入っていたら怖いから、 できれば避けたかった所なのだが致し方あるまい。 #include <iostre
One-liner in Haskell - 純粋関数型雑記帳
Haskellを現場言語にするために、こんなものを作ってみました。 hoe: Haskell One-liner Evaluator （名前には深い意味はありません。） Haskellでワンライナーをやろうという誰得なツールです。誰得ですが、ワンライナーでも、型があると便利なんではなかろうか、型を元にユーザの望みの動作が大体決定できるんではなかろうか、という発想を元に作られました。 Haskellのワンライナーは、ghc -e でも評価できますが、これは (Show a) => a か、 (Show a) => IO a な型しか評価できません。hoeでは、String -> String など、もっと色々な型を評価できます。そして、その型に応じていい感じの動作が自動的に選択されます。 例えば、idを入力すると、入力がそのまま出力されます。 $ cat tmp Hello, Haskell
Lazy I/O must go! - Iteratee: 列挙ベースのI/O - 純粋関数型雑記帳
最近ちょっと気になるiterateeを勉強したので、日本語の解説を書いてみます。と言いつつ、大部分が The Monad.Reader Issue 16 *1 からの引用です。 はじめに Iterateeと呼ばれる新たなI/Oの抽象化手法が、最近にわかに広まりつつあります。既存のI/Oが抱える問題を解決するべくOleg Kiselyovによって2008年頃に提唱されたiterateeは、新しい高性能webフレームワークsnap *2 や、hyena *3 で利用されています。また、HackagDB上にて、iterateeパッケージ*4、およびiterateeを利用できる様々なパッケージ *5 *6 *7 *8 が公開されています。 しかし、ドキュメントの少なさなどからiterateeがどういうものなのかよく分からないという人も多いようです。そういうわけなので、iterateeを易しく解説し
チームラボ天下一武道会 - 純粋関数型雑記帳
チームラボ天下一武道会 ～コードGolf & F1レース！～ : ATND に参加してきました。普段Java使っていないのでどうなるかと思いましたが、なんとか優勝することができました。 問題は、ユーザデータと商品の購入データが与えられるので、全商品間のコサイン類似度を求めよというものでした。入力は <ユーザID>,<商品ID> のCSVで与えられ、出力は商品ID×商品IDの二次元配列をCSVで出します。購入データは1万件、ユーザ数は1000以下、商品数は500以下という制限です。 順位は、実行時間によるスコアとバイトコードのサイズによるスコアの和によって付けられます。それぞれ50点満点で、実行時間は 10秒 (50点) 60秒 (0点) バイトコードのサイズは、 1Kbyte (50点) 6Kbyte (0点) を基準として、線形補完されて決まります。50点満点ですが、基準値を超えた場合は
Haskell binding for MessagePack - 純粋関数型雑記帳
MessagePack の Haskell binding を作りました。 MessagePackとは http://msgpack.sourceforge.jp/ id:viver さんが開発された高速なバイナリシリアライザです。 http://d.hatena.ne.jp/viver/20080816/p1 や http://d.hatena.ne.jp/nobu-q/20091209 が詳しいです。 インストール方法 githubにレポジトリを置いています。http://github.com/tanakh/hsmsgpack にあります。 パッケージをHackageにアップロードしています。http://hackage.haskell.org/package/msgpack-0.1.0 にて公開されています。 インストールは、MessagePackをインストールしてから、 $ cab
Haskellerのためのプレゼンツール"MonadPoint" - 純粋関数型雑記帳
去る11月20日、Haskellナイトというイベント ( http://hop.timedia.co.jp/ )で、"HaskellerのHaskellによるHaskellerのためのプレゼン"というなんだかよくわからないタイトルで発表してきました。 遅くなりましたが、作った物の公開と発表の補足をしておきます。 概要 Haskellでプレゼンツールを作りました。 Haskellで記述され、 スクリプトもHaskellで書く ようなプレゼンツールです。 プレゼンをモナディックに書くので、MonadPointと名付けました。略称は「モナポ」です。 レポジトリ http://github.com/tanakh/MonadPoint にてMonadPointを公開しています。 http://github.com/tanakh/haskell-night にて当日使ったスライドのソースとWindow
C++向け簡易コマンドラインパーザ cmdline - 純粋関数型雑記帳
を作りました。 http://github.com/tanakh/cmdline 何か コマンドライン引き数の解析を助けるライブラリです。同じ目的のライブラリに、Cの標準関数であるgetoptやgoogleのgflagsなどがありますが、cmdlineは適当に使えてそこそこ便利というのを目指しています。getoptは使いにくいし、usageも自分で書く必要がある。gflagsはライブラリをインストールしたり、リンクしたりちょっと大掛かり。cmdlineは、1ヘッダファイルで、コピーするだけで使えて、修正BSDライセンスで公開しているので、自由にプログラムに取り込んでいただけます。 コードサンプル #include "cmdline.h" int main(int argc, char *argv[]) { cmdline::parser p; p.add("hoge", 'h', "hog
2009-09-08
素人なのであてにはならないと思いますが。 Scalaで競技プログラミングを行う際に気をつけることの列挙。 なぜScalaなのか？ 速い 静的型付 字面がC++よりましなのでC++よりは速く書けるであろうという期待 同じ理由でJavaよりは速く書けるであろうという期待 OCamlよりも基本的なライブラリが充実しているので速く書けるであろうという期待 Haskelは配列を弄繰り回すような場合にコードが冗長になる傾向があるのでそういう場合に比較して速く書けるであろうという期待 プログラム全体の構造 Scalaプログラムの実行方法には二通りある。 scalaコマンドによる直接実行 scalac(fsc)コマンドで.classファイルを生成 → scalaコマンドで.classファイルを指定して実行 注意すべきは、どちらの方法をとるかで書くべきプログラムが変わることである。scalaコマンドで直接実
SSD向け全文検索エンジン - 純粋関数型雑記帳
ここのところ私がメインでかかわっていた検索エンジンがリリースされました。 こちらに紹介があります。 http://d.hatena.ne.jp/kzk/20090310 デモとしてWikipediaの全言語(記事が少ない言語は省かれているかも)の全記事 約50GBからの検索を1台のPCで行うものが公開されています。 よかったら試してみてください。 http://demo.sedue.org/wikipediasearch/ 下の方でいくつか数字を出していますが、 正確に計ったわけではないので参考程度にしてもらえると。 ちょこっと宣伝 ボックスに単語を入れると検索できます。 一応、全言語で検索するデモなので、各言語での検索は 全言語の検索結果をフィルタしているだけです。 単語の列を入れると、AND検索できます。 検索速度のデモなので、結果のキャッシュなどはしていません。 すべてのクエリについ
HaskellによるWebアプリ - 純粋関数型雑記帳
http://tanakh.jp/hl/ darcs get http://tanakh.jp/repos/haskellitter/ Haskellでtwitterのようなものを実装しました。 試験的に公開してみます。 皆様利用して感想など頂けると幸いです。 Web2.0的な素敵な背景は、tkngさんに作っていただきました。 ありがとうございます。 全体的なページのデザインは私が適当にポコポコ作ったので、ひどいです。 このシステムは日々の普通な使用にゆるゆると耐えてくれればよいかなと思っておりますが、 最低限のスケーラビリティは考えて設計されております。 投稿データ〜1000万程度まで保持できることを考え、 そのデータに対し現在提供しているあらゆるクエリをノータイムで返すことができます。 投稿、削除、星をつけるなどの操作からランキングをリアルタイムに更新します。 ページはすべてたどること
2004-08-02
なんとな〜くParsecは延期。 引っ張るネタでもないけど… 今回のはいつに無くアグレッシブ。 予定 1:コア編 2:描画システム編 3:(おまけ)サウンドシステム編 その0 概要 はじめに 今年の未踏ユースにて、目的じゃなくて手段が先に来てるとか、 習作ぽいとか、テーマに何か引っかかるものはあるけどPM的にはピンと来ないとか、 散々な理由で採択されなかった私のテーマであったが、 (というか、習作の感がぬぐえないとかそういうのが落とす理由になるとは 思いもよらんかったですよ。あれだけチャレンジしろチャレンジしろって書いておいて) この世界がいつまでたっても退屈な言語に支配されている現状を 黙然としているのにはやはり耐えられず、 Haskellがそのような言語に対していかなるアドバンテージを持っているかを 実例とともに示す必要があると思いこれを書くことにした。 とはいえ 別にこれ、応募時から
2006-08-26
なんだか四月以降文章を書く気分になかなかなれなくて、 二年ほど前、このブログの開始当初の目標だった ひたすらテクニカルアーティクルを載せるページを作るというのは もうすでにかなり頓挫している風ではありますが、 リハビリのために無理に書くことを見つけてでも なにやら書いてみることにします。 ところで、先月の末から一月ほど京都に帰っていたのですが、 京都は死ぬほど暑かったですね。 盆地で暑いと言われつつも、 やはり離れてはじめて分かるというものです。 (私はあんまり広く情報収集したりしないので、 ここに書く内容はとうによく知られた問題なのかもしれないが、あしからず…) プログラムの実行において、何らかの外部的な情報 (つまりIOを介して得られる情報)を そのプログラム全体から参照したいケースというのがある。 典型的な例がプログラムのコンフィギュレーションで、 たとえば、設定ファイルから設定値を
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
