この記事はMLアドベントカレンダー22日目の記事です。 プロローグ autotakerはHaskellのList.sortが遅いので嘆いていた。 あまりに遅いので簡単なコードを書いて実験することにした。 gist082402e29104b2f21a6d $ wc test300000.in 300000 300000 2994897 te…

問題 つなぐと 2622440554406490912 + 0147433867683690946 = 4258610457570922687 などと表示される。数字は３秒おきに更新される。 解法 もらったソースを読む。 while 1: x = pow(random.randint(1000000000, 9999999999), n, (n * n)) o = (pow(n + 1, 1…

チームnegainoidoで参加しました。チームメンバーはautotaker, atetubou, cympfh, garasubo, isurugieri, tailedだった。 atetubouとtailedは台湾旅行（ICPCのアジア地区予選）中だったので遠隔参加でした。 コンテスト開始時 開始直後にatetubouがStart SEC…

概要 最近、CodeRunnerというAIコンテストの予選BでJSONデータをいじる必要が出てきたのでHaskellでJSONを読めるようにAesonを触ってみた。さらにTemplateHaskellを用いてレコード型の定義からJSONデコーダを自動導出できるようにしてみた。 背景 予選Bの問…

概要 CPS変換とはラムダ項と継続を入力として型Xを持つラムダ項を出力するプログラム変換である。 HaskellのGADTという機能を使うと型Tを持つラムダ項を表すデータ型Term Tを定義できる。 CPS変換が正しいことは cps :: Term T -> Term ([T] -> X) -> Term X…

構文木に情報を追加したいときにFix使うとちょっと楽だよっていう話。 例えば data Term = Var String | Lam String Term | App Term Termみたいなデータの各ノードにIdを振りたいとする。 ナイーブにやると data ITerm = IVar Int String | ILam Int String…

導入 以下のBNF*1は足し算とlet式からなる式を表す。 <digit> ::= [0-9] <alphabet> ::= [a-zA-Z] <int> ::= <digit> | <digit><int> <id> ::= <alphabet> | <id> <expr> ::= <int> | <id> | '(' <expr> ')' | "let" <id> '=' <expr> "in" <expr> | <expr> '+' <expr>さて、この文法には２つの曖昧性がある。一つは足し算の結合性、もう一つはlet式と足し算の優先順位の曖昧</expr></expr></expr></expr></id></expr></id></int></expr></id></alphabet></id></int></digit></digit></int></alphabet></digit>…

概要 プログラムで画像を作りたい時に便利そうなのでメモ。diagrams-svg: SVG backend for diagrams drawing EDSL. | Hackage これはHaskellでVector画像を描くライブラリである、diagramsライブラリのSVG出力ライブラリとなっている。 diagrams-lib: Embedd…