週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

USJいってきました。 ターミネーターの3D映画がそれなりに面白くて満足。前説の人がまた結構よかった。

USJの評判を調べたら奇妙な記事が。

  • 宮村優子(声優) - Wikipedia
    人気の高さゆえか各種の真偽不明な目撃遭遇情報が絶えず、都市伝説の観すらある。代表的なものに、「夫の職場であるUSJでアトラクションのガイドである綾小路麗華役をしている」がある。
スポンサーサイト
Summary of SRM 390よいまとめサイト。

追記

topcoder知らない人に解説~。topcoderの単発戦Single Round Match(略称SRM)は、div. 1 とdiv. 2の二部構成で行われています。初めて参加する人や成績の余りよくない人はdiv. 2に、成績のよい人はdiv. 1に参加します。何回か参加して成績が変わると、次回から参加するdivisionが変わります。上のページは今回のSRMに参加した日本人の成績がまとまっていて、私は一位に載っていますが、それはdiv. 2の一位です。div. 1はdiv. 2とは比べ物にならないくらい難しく、魑魅魍魎歴戦の猛者が集まっております。私は次の試合から、そのdiv. 1の末席を汚すことになります。

つまり、私の冒険はまだ始まったばかりです。一位に載っているように見えますが、まだそれはあんまりすごくないです。

さらにいうとこのリストには日本人しか載っていません。Topcoder staticticsを見ると、div. 2でも私よりもっと上の人がたくさんいますです。div. 2の1000点問題を解いた人も(一人だけですが)います。

今まで、seqAllを次のように使えるものとして実装しようとしていました。valueが正則評価すべき値、Typeがその値の型です。

$(seqAll $ reifyType Type) value others

この実装はおかしいです。また、Template Haskellを使えば実現できると思っていましたが、それも間違いで、実現不可能です。

  1. valueの型を明示的に指定するのは辛すぎます。複雑な型のコンポーネントすべてを強制的に評価するところが売りの関数を動かすのに、複雑な型を正確に指定しろとかおかしいです。
  2. Template Haskell のreify*の引数は直書きした型とかData型の名前しか許されません。map reifyDecl (Dataのリスト)のようなことはできず、reifyDecl Treeと書くことしかできません。

やはり型クラスを基礎に書いたほうがよさそうです。ちょっと考え中。

SRM 390に今朝2時から。初参加なのでDiv. 2で参加です。

初参加前に過去問を解いてみました。結果としては全部解けたものの時間ぎりぎりで、しかも250点以外はSystem testを落とすという体たらく。250点問題も、はじめ問題を誤読していて、面倒なDPを書いていました。正しく読めていれば10分せずに片がつくはずです。とりあえず、

  • 問題はよく読む。特にサンプルは手で解いてみる。
  • 範囲ぎりぎりのテストケースを入れる。
という普通の教訓が得られました。本当になまっています。もっとも、問題をよく読むとかコンテスタント時代もよく反省した覚えがあります。

練習の成果なのかコンテスト本番はDiv. 2で54位、部屋一位。rateは1468もらいました。まだblue coderなのでつぎもdiv. 2なのでしょうか?どこからdiv. 1になるかわかりません。

問題のメモを次に。

Template Haskellを調べてみました。直前のseqAllに使えるかと思いまして。

Template HaskellはHaskell用のテンプレートプログラミングあるいはマクロです。Haskellのプログラム中に「Haskellコードを生成するHaskellコード」を貼り付けてコンパイル時に実行します。lisp/schemeのマクロとかc++ templatesと同じのりです。lispのマクロがc++のtemplatesでないように、Template Haskellもそれらとは結構違いますが。

Template Haskellを使えばたとえば次のコードがかけます。

  • n-タプルのm番目を選択する関数sel n m。$(sel 1 3) (x, y, z) == x
  • zip, zip3, zip4などを統一的にできるzipN。$(zipN 3) == zip3
  • 上のzipNを1からNまで一度に宣言するgenZipN。

上のコード例にあるように、Template Haskellの部分は$(..)で囲まれています。この部分がコンパイル時に評価され、その結果のHaskellプログラムがここに挿入されます。

  • 引数によって型が変わる関数が定義できる。上の例を参照。
  • Template Haskellによって生成されたコードにはちゃんと型検査が行われる。 $(sel 1 3) (x, y)と書くと型エラーになる。
  • 引数に変数は入れられない。\x -> $(sel x 3)なんてコードはかけない。

とりあえずちょっと地味な例として、template haskellで書いたprintf関数が論文の頭に載っています。haskellにはすでにText.Printfモジュールにprintf関数を持っているので、それとの比較をしてみます。

まずは普通のprintfを使ったコードから。

import Text.Printf
main :: IO ()
main = do
    let x :: Int
        x = 3
        y :: Int
        y = 4
    putStrLn "trial: 1"
    printf "variable %s = %d\n" "x" x
    putStrLn "trial: 2"
    printf "variable %s = %s\n" "y" y

実行してみます。

>ghc --make NormPrintf.hs
Linking NormPrintf.exe ...

>NormPrintf.exe
trial: 1
variable x = 3
trial: 2
NormPrintf.exe: Printf.printf: bad argument
次にTemplate Haskellで書いたPrintfを使ってみます。
import ThPrintf (printf) -- definition of printf.
main :: IO ()
main = do
    let x :: Int
        x = 3
        y :: Int
        y = 4
    putStrLn "trial: 1"
    putStrLn ( $(printf "variable %s = %d") "x" x)
    -- putStrLn "trial: 2"
    -- putStrLn ( $(printf "variable %s = %s\n") "y" y)
実行してみます。ghcでは、コンパイラオプションに -XTemplateHaskellをつけるとTemplate Haskellが有効になります。
>ghc --make -XTemplateHaskell TPrintf.hs
[2 of 2] Compiling Main             ( TPrintf.hs, TPrintf.o )
Loading package base ... linking ... done.
Loading package array-0.1.0.0 ... linking ... done.
Loading package packedstring-0.1.0.0 ... linking ... done.
Loading package containers-0.1.0.0 ... linking ... done.
Loading package pretty-1.0.0.0 ... linking ... done.
Loading package template-haskell ... linking ... done.
Linking TPrintf.exe ...

>TPrintf.exe
trial: 1
variable x = 3
ちなみに、ソースの中のコメントアウトを除くと、次のようにコンパイルエラーになります。
>ghc --make -XTemplateHaskell TPrintf.hs
[2 of 2] Compiling Main             ( TPrintf.hs, TPrintf.o )
Loading package base ... linking ... done.
Loading package array-0.1.0.0 ... linking ... done.
Loading package packedstring-0.1.0.0 ... linking ... done.
Loading package containers-0.1.0.0 ... linking ... done.
Loading package pretty-1.0.0.0 ... linking ... done.
Loading package template-haskell ... linking ... done.

TPrintf.hs:12:47:
    Couldn't match expected type `[Char]' against inferred type `Int'
    In the second argument of `$(printf "variable %s = %s\n")', namely
        `y'
    In the first argument of `putStrLn', namely
        `($(printf "variable %s = %s\n") "y" y)'
    In the expression: putStrLn ($(printf "variable %s = %s\n") "y" y)

まず、Template Haskellのprintfだと、引数を間違えると型エラーが生じます。標準のprintfは実行時までエラーがわかりません。これは便利。その一方で、printfのフォーマットを動的に変えたりすることができなくなります。

Template Haskellの便利さがわかりましたか?私にはまったくわかりません。そもそもすでにあるprintfを作ってもまったくアピールになりません。もっとえぐいものが必要です。

使用したOSはWinXPSP2Home, コンパイラはGHC 6.8.1でした。

printfのソースを続きに貼ります。元論文にこれの作りかけのものが貼ってあります。

以前のHaskellの例外の記事を書いたときから考えていたことなのですが、ある値の要素をすべて正則評価する関数は書けるのでしょうか。値がただのIntやDoubleなどならそのままseqで評価して、タプルやリストならその要素をすべて評価するというようなものです。コードにすると次のようになります。

xがIntやDoubleなど、構造を持たない型なら
seqAll x y = seq x y
リストを引数にすると、次のようにリストの中身を正則評価します。タプルも同様。
seqAll [] y = y
seqAll (x:xs) y = x `seqAll` xs `seqAll` y
さらに、複雑なデータ型を分解します。
Data Tree a = TreeLeaf | TreeNode (Tree a) (Tree a)
seqAll TreeLeaf y = y
seqAll (TreeNode a b) y = a `seqAll` b `seqAll` y

注目してほしいのは、リストを引数としたときの右辺はseqAllになっていること。このため、リストのリストがきたときも、その中身をすべて正則評価します。

明らかに無茶なのが最後の例です。Haskellではそんな無茶なコード生成はサポートされてません。最後の例以外は何とかなるでしょうか?

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。