Hatena::ブログ(Diary)

純粋関数型雑記帳 このページをアンテナに追加 RSSフィード Twitter

このページはHaskellを愛でるページです。
日刊形式でHaskellなどについての記事をだらだらと掲載しとります。
2004 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 11 |
2007 | 03 | 04 | 05 | 07 | 08 | 09 | 12 |
2008 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 03 | 05 | 06 | 09 | 10 | 11 | 12 |
2010 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 12 |
2011 | 01 | 02 | 05 |
本体サイト

2005年09月30日(金) ICFP

[]ICFP 結果発表 ICFP 結果発表を含むブックマーク ICFP 結果発表のブックマークコメント

先日ICFPの結果が発表された。

http://icfpc.plt-scheme.org/

うちのチームは今年も三位。

去年と順位変わってない、といいつつ

今年は三位まで表彰されるので、実は入賞していたりする。

チーム名はなぜかCombat探偵団。

なんで探偵団なんだ。


というかねぇ。ほんとは入賞したもんで

エストニアに招待されていたわけなのですが、

うちの大学はけち過ぎます。

理学部だから、とか、同大学院に行かないかもしれないから、とかで

お金が出ません。ほんとけちです。

一位と二位のチームはしっかり出席してます。

寂しいです。


トップは今年もHaskellだった。

良かった。これで今年も虎の威を借ることができます。

多かった言語C++ OCaml Python Java Haskell C Perl

これについては言いたいことがいろいろと。

明日に続きます。


NaNaIRoさんはk.inabaさんでしたか。

pre-twistでは三位だそうで、

そのまま作っていれば、というところでしょうか。

(pre-twistではうちのチームはぼこぼこですな…)

いや、強い弱い以前に、今回はっきり言って

まともなプログラムを書きさえすれば、

というところがあるので、(これも後述)

まぁ、残念といえば残念ですね。


うちのチームはpre-twistのround2では惨敗…

大体スコアの分布を見ていると、Robberが生還すれば3000点ぐらい、

Copが5試合分頑張って点をかき集めて3000点ぐらい。

丁度均等に得点が取れるようになっているけど、

Robberのほうはかなり博打。

Copはどんなときでもある一定は得点が入るけど、

Robberはつかまったら0。

つまり最終的なスコアは大体(0 or 3000)+Copによる底上げ、ぐらい。

pre-twistのround2ではRobberは一度も生還していない…。正直ひどい。

twistバージョンではかなり生還率が上がっている。

たぶん、苦し紛れに銭投げをしまくったり

Copを悪に引きずり込んだりしているのが効いているのか。

銭投げをしまくっている分スコアもだいぶ下がっているけど、

銭投げを減らすと死亡率が上がりそうだし、

この辺はなかなか難しいところ。

結局はもっと賢い逃げルーチンを作れという話だ。


今回、日本からの参加者が少なくなったような

感じがあったんだけども、結局10チームは出たそうで。

意外と少なくなかった。というか、世界で4番目やね。


というわけで、今回は三位。

見事Haskellに称号ももらえたので、

ここで公に自慢してしちゃいます。

これはいいとして…(自分がもらった称号だけど…)

今年も目利きのハッカーが選ぶ言語

やっぱりHaskelはすごいや。


ところで、今年は二位に知らない言語ランクイン。

Dylan という言語。しかも特別賞ももらっている。

Dylanは一チームしか使っていなくて、その一チームが入賞

これこそDylanがすごいのかDylanを使った人がすごいのか

良くわからないことになっているが、

サンプルが少なすぎる、というのが結論で。

とりあえずDylanというのがどんなものなのか勉強してみようとは思う。


(以下、いろいろと明日分に続く)

yaneuraoyaneurao 2005/10/01 14:31 おめでとうございます! > 入賞

Dylanは10年ぐらい前にコンパイラを作ろうとしたときに参考にした覚えが..。確か、動的オブジェクト指向言語ですネ。実行コードにまでは動的オブジェクトを持ち込まないので、比較的速いコードが生成される(はずです)。多値を関数の戻り値とできたり、局所関数が使えたり..。

tanakhtanakh 2005/10/03 00:32 なるほど。結構昔からある言語なんですね。
しかし、現状ではあんまり使われていないようですね。
関数型の特徴もいくつか持ち合わせているんでしょうか。
とりあえずちょっと勉強してみます。

2005年09月20日(火) 演算子 <?= >?=

[]演算子 <?= >?= 演算子 &lt?= &gt?=を含むブックマーク 演算子 &lt?= &gt?=のブックマークコメント

C++暦7年の私ですが、この度新しい演算子を覚えました。

<?= と >?= です。


これはそれぞれ、

a<?=b; => if (b<a) a=b;
a>?=a; => if (b>a) a=b;

あたりの意味のようだ。

ようだ、というのも、この演算子、どこにも載っていません。

最近のC++仕様にあるものなのか、GCCの拡張なのか。

記号が記号だけに、Googleで調べることができない。


しかしまぁ、これで

a=max(a,b); というのを書くのが多少楽になりそうだ。

というか、それ以上でも以下でもないこの演算子

いったいそれ以外のどこで使えというのだろうか。

ACAC 2005/09/21 01:39 つhttp://www.chemie.fu-berlin.de/chemnet/use/info/gcc/gcc_9.html#SEC99

ちゅんちゅん 2005/09/21 01:52 先を越されたけどhttp://www-cms.phys.s.u-tokyo.ac.jp/~naoki/CIPINTRO/gccextend.htmlとか。

tanakhtanakh 2005/09/22 00:24 やはりGCCの拡張でしたか。
<? >? という演算子があるんですね。
それで a<?=b -> a=a<?b ですか。なるほど。

トラックバック - http://d.hatena.ne.jp/tanakh/20050920

2005年09月19日(月) Functional Online Judge

[]Functional Online Judge Functional Online Judgeを含むブックマーク Functional Online Judgeのブックマークコメント

Haskellでオンラインジャッジしたいよね?

ということでこんなものができました。

http://tanakh.ath.cx/OnlineJudge/oj.cgi/

あらかじめお断りしておきますが、

いつ公開が終了するかも、いつデータを消すかも分かりません。

ジャッジシステムデータベースの排他処理で落ちることがあるので、

いつ落ちているかも分かりません。

なるべくジャッジ中にはページを参照されませんように。

あと、ネットワークマシン環境ともに貧弱なので、

あまり負荷をかけられませんように。

ハッキングしようなどとも思われませんように。


とりあえず、うちのしょぼいマシンでは動かすのも大変なので、

私にサーバを貸してくださるという方、

オンラインジャッジを運営したいという方、

もしそんな奇特な方がいらっしゃれば、いつでもご連絡ください。

あと、私のデザインセンスが皆無なので、

もっとかっこよくしちゃる、という人も是非どうぞ。


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

以下、技術的な話


このCGIは(おそらくもちろんというか)Haskellで書かれている。

Haskellコンパイルできるので、コンパイルして実行している。

そのため、実行速度はなかなか速い。

種種のスクリプト言語よりおそらく速い。

Haskellsqliteを用いてデータベースアクセスをしつつHTMLを生成するという形である。


HTML生成に関してはNetwork.CGIとText.Htmlコンビネータライブラリを用いると

非常にすんなりと実装できる。

Session周りのサポートがないので、その辺は困る。

自分で書かないといけないか?

WASHって便利?

ちなみに、Network.CGIのwrapperにバグを発見した。

バグを発見したのだが、どこにどうしていいものやら分からないので、

こっそり直して使っている。


データベースアクセスはHaskellDBを用いた。

裏はsqliteだが、まぁ、普通に使えている。

しかし、HaskellDBも微妙にしょぼい。

limitで個数しか指定できない。

開始位置を選べないと、10件目〜20件目を取ってきたい、

みたいな時にlimitに20を指定して取ってきたやつを(Haskellで)dropするしかない。

開始位置が10ならいざ知らず、数万のオーダになると厳しいと思うのだが。

あと、group byが使えない。

group byが使えないと、特定の要素が何個あるのかカウントするのに、

いちいち引っこ抜いてきて(Haskellで)lengthしないといけない。

ひとつならそれでも仕方がないが、カウントする対象が

いくつもあった場合、非常に計算の無駄だ。

用意されている関数だけで何とかうまいことできないか考えたが、

どうも無理っぽい。

あと、これもバグっぽいのだが、

同じ名前をもつキーをprojectできない。

仕方がないので、そこだけ名前を変えたりした。


とりあえず使ってみた総評は、

「今一歩?」

という感じだ。

もうちょっと痒いところに手が届いて欲しい。

まぁ、でも、コンビネータ言語によるHTMLの生成は快適そのものだし、

SQLクエリのコンビネータによる生成も(痒いところ以外は)快適だ。

なにより、書いてて楽しい。

もうちょっとライブラリが整備されていれば非常に良い。

y_saway_sawa 2005/09/20 15:13 Ocamlの採点なんですが、Judgingで止まってしまいました・・・
一応、PKUのOnlineJudgeでAcceptされたJavaのコードと出力は同じなので間違ってはいないと思うのですが・・・・

tanakhtanakh 2005/09/20 17:34 なんだか、database is locked というエラーでジャッジシステムが落ちてしまってます…。つまり、ジャッジシステムが結果を書き込みながらCGIをロードしたらおかしくなるんですけど、これは直さないといけませんね…。

oxyoxy 2005/09/23 16:56 コンパイルする際に、ghc --makeとしてもらせませんか?1003解くのにStateモナド使ったら弾かれてしまいました…。

tanakhtanakh 2005/10/01 08:58 確かにリンクで失敗していますね。--make は必要なライブラリをリンクしてくれるんですかね?つけるとコンパイルは通るんですが。-package data でも通りますけど、あんまりこの辺知らないので…。とりあえず --make をつけるようにしてみました。

トラックバック - http://d.hatena.ne.jp/tanakh/20050919

2005年09月09日(金) HSDL

[]HSDL HSDLを含むブックマーク HSDLのブックマークコメント

CabalとHSCについて知ったので、

GHC6.4では使えなくなっていたHSDLを

( http://fxp.hp.infoseek.co.jp/haskell/HSDL/ )

Cabalに対応したり、いろいろした。

とりあえずGHC6.4で動くようになったので、これでよしとする。


というわけで、わき道にそれたが、

HSQLも微妙に進展した。ソース中の

#if defined(_WIN32_)

というところを

#if defined(_WIN32)

に直すと、とりあえずコンパイルはできるようになった。

これが分かるまでどれだけ苦労したか…。

というわけで、一応コンパイルはできたが、

次はリンクができない。

もう本当にどうすれば良いのか。

[]昨日のHSQL 昨日のHSQLを含むブックマーク 昨日のHSQLのブックマークコメント

いろいろやっているうちになんとかリンクはできるようになった。

とりあえず、前段階で何でリンクできなかったかというと、

GHCが持ってるmingwにWindowsネイティブ版MySQLのライブラリが

リンクできなかったということ。

mingwに渡せるライブラリを作ることはほぼ不可能っぽいので、

DLL版のほうからインポートライブラリを作成して

ごちゃごちゃやればいけた。

というか、ここに書いてあった。

http://www.synnottsoftware.com/tutorials/mysqlwindows.php

Cygwin or mingwでWindows版MySQLとリンクする方法だ。


で、リンクできたは良いものの、

connectを呼び出すと落ちる。

main.exe: internal error: resumeThread: thread not found
    Please report this as a bug to glasgow-haskell-bugs@haskell.org,
    or http://www.sourceforge.net/projects/ghc/

thread not found てどういうことやねん。

これは、

{- OPTIONS -fffi -}

#include <ghcconfig.h>

import Foreign
import Foreign.C

#include <windows.h>
#include <mysql.h>

type MYSQL = Ptr ()

foreign import ccall "mysql.h mysql_init" mysql_init :: MYSQL -> IO MYSQL

main = do
  pMySQL <- mysql_init nullPtr
  return ()

のような簡単なソースでも落ちるので、

多分GHCからmysql_initを呼び出すと起こってしまうのだろう。


こんなのどうすればいいのか、

というわけで、調べてみたら、こんな記事が見つかった。

http://www.mail-archive.com/glasgow-haskell-bugs@haskell.org/msg05881.html

投稿日二年前なんだけど。

いやいや、すぐ直すって書いてあるやん。

というか、6.2で直ってるって書いてあるのに、

6.4でも発現するというのは一体どういうこと?


さて、結局どうすればいいんだろうか。

2005年09月08日(木) HSQL

[]HSQLが入らない HSQLが入らないを含むブックマーク HSQLが入らないのブックマークコメント

久々に作りたいものができたので、

そのためにデータベースソフトインストールして

それを何らかの言語からいじれるようにしようと思った。

最初PostgreSQL+Gaucheでやろうとしたのだが、

まずいきなりPostgreSQLインストールで詰まった。

Cygwin上で動かそうと思っていたのだが、

PostgreSQLCygwin入れたら勝手に入っているので、

起動させれば良いだけだろうと思って

手順を調べてそのとおりにやってみるも、うまくいかない。

なんでだー、と調べることしばし、

なんと、Cygwinの1.5.18-1ではPostgreSQLは落ちるらしい。

回避法は

バージョンを古くする

スナップショットを取ってくる

・新しいバージョンが出るまで待つ

…どれも話にならない。

もういいや、PostgreSQLやめ。

ということで即効でMySQLに鞍替え。

MySQLをいろいろ調べてみると、

どうもWindows版のほうがCygwinコンパイルしたものよりも

安定していて良いらしい。

というわけでMySQLインストーラインストールするだけ。

ならPostgreSQLWindows版を使えよ、という話であるが、

まぁ、もう何でもいいや…。


それで、MySQLが入ったので、次にGaucheDBIライブラリ

インストールしようとしたのだが、ここでまた詰まる。

どうやらコンパイルするためにlibmysqlclientというものが必要らしいのだが、

WindowsMySQLインストールしたら、Cygwinで使えるライブラリは入らないらしい。

そういうわけでこれまたいろいろ調べたところ、

MySQLソースを取ってきて、クライアントだけ

Cygwinコンパイルしないといけないようだ。

ようやくコンパイルしてインストールできて、

さぁやっとプログラミングできる、と思いきや、

Gaucheからデータベースへの接続ができない。

よく分からない例外で落ちる。

これまたいろいろ調べるもぜんぜん分からない。

(というか、資料自体が数えるほどしかないんだけど…)


あああ、もういいや。Gaucheやめ。

というか、なんでGaucheにしようと思ったのか。

HaskellSQLを扱うライブラリなかったかいな、

とまたまたいろいろ調べてみると、

HaskellDBというなんだかすごそうなものがあった。

コンビネータライブラリSQLの構文をごちゃごちゃできたりするらしく、

おお、これでいいやん、というわけで、インストールすることに。

しかしこれはHSQLというのを必要とするらしい。

それで、そっちを先にインストール


HSQLの最新版はCabalというシステムを使っていて

ビルド方法がちょっと特殊だが、HSQLライブラリは難なくインストールできた。

しかし、もうひとつ必要なhsql-mysqlのほうがコンパイルできない。

Cygwin上で実行しているのだが、そこからさらにrunghcを起動しているので、

Cygwinパススクリプトに見えない。

(GHCWindowsネイティブ版を使っている)

CygwinやらWindowsネイティブやらを混在させているので

もう本当にややこしくてたまらんのだが、

とにかくGHCCygwinパスが見せられないので、

WindowsのほうのPATHを書き換えてみたり、

Cabalが生成するファイルを書き換えてみたり、

Cabal自体のスクリプトを書き換えてみたり、

いろいろやって、ソースが読み込んでるヘッダファイルが見えるようにはなった。

しかし、ヘッダが見えてもコンパイルが通らん。

コンパイルしようとしているファイル拡張子hscファイル

(これ、どういうファイルか知らないんだけど…)

なんだか、途中に #include <XXXX> てな感じで

Cのヘッダファイルをインクルードしている。

Haskellソース中でCのヘッダをインクルードしたらどうなるのか

よく分からないのだが、とにかくその中でエラーが出てコンパイルが通らない。


いろいろ試したり調べたりしたものの、

そもそもHSQLは総ダウンロード数が100回未満だったり、

(やはりHaskellプログラマ希少種なのか?)

メーリングリストには最新版が出てから4回ぐらいしか書き込みがなかったりで、

どうやって良いのかさっぱり分からない。


そんなこんなで結局一日が終わってしまった。

どなたか詳しい方、HSQLのWindowsへのインストール方法、

あるいはHaskellデータベースを扱う方法を教えていただけると助かります。

ikegamiikegami 2005/09/09 15:12 coLinux いいよ。
http://colinux.sourceforge.net/
私はここを参考にインストールしました。
初期設定(特にネットワークまわり)が面倒ですけど、入れたら
あとは快適です。
http://scratchpad.fc2web.com/colinux/

ikegamiikegami 2005/09/09 15:13 つまり、cygwin をあきらめて coLinux にしたら、ということです。
先にそれを言うのわすれてた

tanakhtanakh 2005/09/09 22:21 うーん。CoLinuxですか。
それは最終手段にしたいんですけどね…。
なんとかWindows上でできる方法をもうちょっと考えて見ます。

yaneuraoyaneurao 2005/09/10 10:07 |´)っ VMWare(or VirtualPC) + coLinux on Windows

shelarcyshelarcy 2005/09/10 10:21 mingw32lib 内にライブラリとヘッダを入れておくという形なら、以下の方法で SQLite を使うことはできます。
ただし、HaskellDB が SQLite3 に対応していないことになっているので、SQLite3 を使う場合には import qualified Database.HSQL.SQLite のところを SQLite3 に書き換えてやる必要がありますが。
(SQLite と SQLite3 用のバインドは同じ API になってます。)

Setup.lhs
#!/usr/bin/runghc

¥begin{code}
import Distribution.Simple
main = defaultMain
¥end{code}

SQLite3.cabal
name: hsql-sqlite3
version: 1.0
license: BSD3
author: Krasimir Angelov <kr.angelov@gmail.com>
category: Database
description: SQLite3 driver for HSQL.
exposed-modules: Database.HSQL.SQLite3
build-depends: base, hsql
extensions: ForeignFunctionInterface, CPP
include-dirs: ../mingw32lib
extra-libraries: sqlite3
extra-lib-dirs: ../mingw32lib

tanakhtanakh 2005/09/10 18:05 coLinux出すのはもうちょっと頑張ってから…
SQLiteならいけますか。なるほど。
SQLiteというソフトを聞いたことがなかったので
敬遠していたのですが、とりあえず使ってみることにします。

2005年09月04日(日) 大それたことを・・・

[]勝っちまったらしいですぜ? 勝っちまったらしいですぜ?を含むブックマーク 勝っちまったらしいですぜ?のブックマークコメント

なんか、Winnerリストに入ってるよ、というメールが来てしまった。

うーーーむ。これは…。

まさかあんなので勝てるとは思っていなかった…。

(13人チームで5万行もOcamlコードを書いたというところがあって

ガクガクブルブルしていたのだが)


候補は、

・Judges' Prize

・first prize

・second prize

・third prize


さて、おそらく三等賞だと思うけども、

幾らかはお金がもらえるんだろうか。

少なくとも、今年も「Haskell最高!!」を

言いふらせる権利はもらえるわけだ。


…とまぁ、詳しいところはまだ良く分からんのだが、

去年3位、今年入賞(更にICPCのParallel Challenge2位も)となると、

私たちは本気でAIプログラミングの才能があるんじゃないのかと

思ったりなんかしちゃったりするのだが、どんなもんなんだろうか。

mayahmayah 2005/09/05 13:05 おめでとうございます!
combat の人たちは、思いついたことをすぐにコードに落とせるという印象があります。ICPC, ICFP など、短い時間の中でコードに書けるという強さと、AI のアルゴリズムを思いつく能力の高さに脱帽させられるばかり。今年私は投げてしまいましたが、来年はもうちょっとなんとかします……。

tanakhtanakh 2005/09/06 04:20 ありがとうございます。
私の場合はすぐにコードに書けるようなことしか考えていない、とも言いますかね…労力対効果?のバランスがよいのかもしれません。
来年も出ようと思ってますので、是非ともともに頑張りましょう。

トラックバック - http://d.hatena.ne.jp/tanakh/20050904

2005年09月02日(金) Google Code Jam Round 2

[]Google Code Jam Round 2 Google Code Jam Round 2を含むブックマーク Google Code Jam Round 2のブックマークコメント

負けた…

http://fxp.infoseek.ne.jp/img/gcj_2005_r2.png

-----

今回の問題は300点、450点、1000点の3つ。

時間は前と同じ75分。


300点問題は、

迷路の中を複数のプレイヤーが陣形を崩さないように探索するとき、

誰か一人がゴールにたどり着くまでの最短距離を求めよ、というもの。

普通に幅優先で終わりかと思われるが、

いろいろとめんどくさい。とてもめんどくさい。

ついに300点問題でこの難易度になったか、としみじみ思う。

35分もかかってSubmit。


この時点で3問解くのをあきらめる。

400点問題は

function hash(bits)
  set key = 0
  prepend '0' to bits
  for( i = 1 to lengthof(bits)-1 )
    if(bits[i-1]=='0' and bits[i] == '0') key = (key * mults[0] + adds[0]) % size
    if(bits[i-1]=='0' and bits[i] == '1') key = (key * mults[1] + adds[1]) % size
    if(bits[i-1]=='1' and bits[i] == '0') key = (key * mults[2] + adds[2]) % size
    if(bits[i-1]=='1' and bits[i] == '1') key = (key * mults[3] + adds[3]) % size
  end
  return key
end

というアルゴリズムに基づきハッシュを生成する。

nビット以下のすべてのデータに対してハッシュを生成したとき、

もっとも多く生成されたハッシュの生成回数を求める、というもの。

ちなみに、ビット数は50まで、sizeは10000まで。

これは、nビットまでの頻度表(と直前のビット)があれば

n+1ビットに対するものが求まるので、DPできる。

これは思いついたら割とすぐ実装できて、

開始1時間ほどでSubmit。


残り時間が少ないので1000点問題は解ける気がしなかったが、

一応少しは考えてみた。

p1 .. pn が与えられたとき、

k1^p1, .. , kn^pn (k>=2, i!=j => ki!=kj)

をすべて約数に持つ最小の整数を求めよ、というもの。

たとえば、{2,2,2} なら 答えは 36。

(2^2, 3^2, 6^2 と選んだときが最小)

制約条件は、n=10までだということと、答えはlong longに収まるということ。

時間まで考えるも、うまい方法はさっぱり思いつかず。

DFSで間に合っちゃうのかなぁ、とか思ったり思わなかったり。


というわけで、Coding Phaseが終了。

続いてChallenge Phase。

ほかの人のコードを見てみるが…。

ぜんぜん間違いが見つからない。

さすがにRound2ともなるとあからさまな間違いをやらかす人はいないのか。

それから大体全員分のコードを見るも、結局おかしいところは見つからず。


程なくしてシステムテスト

システムテスト前の順位が120位ぐらいだったので、

上位が落ちればどうなのかなぁ、といったところ。

さすがに参加者が少ないので、あっという間にシステムテストが終わり、結果が出た。

1000点問題そもそもSubmitしている人が20人ぐらいしかいなかったが、

最終的に通ってる人は2人しかいなかった。

やっぱりとんでもなく難しい問題だったんだなぁ。

で、私はというと…。300点が落ちてた…。

どんな入力で落ちてたかというと、

{".."}というような、プレイヤーもゴールもないような入力だった。

こういう場合は放っておいてもうまくいくと思い込んでいたが、

どうもだめだったようだ。サブミットする前に

プレイヤーがいなければはじいておこうかとも思ったのだが、

プレイヤーがなくて、ゴールだけあるやつがうまくいっていたので、

大丈夫なのかなぁと思い込んでしまっていた。

ああ、だめだ。


しかし、300点問題が通っていれば得点は430ほどになり、

大体90位で通過していたことになる。

惜しかった。かなり悔しい。

とりあえず今回の教訓は、フェイルセーフに実装しろ、ということだ。

今回はプレイヤーがないときにはじいていれば通っていたんだから。

ACAC 2005/09/02 15:16 えーと、ss を set ではなく queue にしないと BFS にならないので、最適解は求まらないんじゃないでしょうか?

tanakhtanakh 2005/09/02 16:23 ああ、本当ですね。
queueにしないとシステムテストをパスしませんでした。
しかし、二箇所も間違えているとは…。
諦めも付きやすくなりました。