ToDoの山が２，３を残して片づいたので、しばらく自分的に夏休みモードということに
します。とりあえずこの機会に、買ったっきり読んでいない本を片づけてしまおう、
と思い立ちました。現時点の未読本を積み重ねてみたのが左の写真です。
３日前に買った本から３年前に買った本まで取りそろえております。 ダークタワーなんてⅢ以前のストーリー忘れてるなあ。 今すぐ読まねばと思って買った本や軽く読めそうな本は当然ながらすぐに 読んでしまうので、「腰を据えてかかろう」と思った本だけが残りがちで。 我ながら自分の本棚から湧いてきたラインナップに見えません。 とりあえずOSから自作するか。
「いやいや今年の夏はこれを読むべし！」というオススメ本の情報もお待ちしておりますです。
明日午後からは研究室にいるのでその時にでも…＞匿名希望25歳・男さん
ちゅーかこの通信ルートに対する効果的な返信方法を開発してください。
筒井ファンとしては気になる一作…ということで、 『時をかける少女』 を見てきました。評判を聞く限りではどなたもほとんど手放しで褒めておられるので 、かなり期待して行きましたが、期待以上でした！
笑いどころで劇場全体が笑いの渦につつまれる映画っていいよね、っというか。例えば ITmediaの記事の４～６番目の画像のY字路のシーンでしたけど、物語の流れとしても 一番重要な分岐点で、そういうここぞというところで、重くて切ない要素とコミカルで 明るい要素を同時に織り交ぜて盛り上げてくる。うまい描き方だなーと。
ストーリーは…、ラベンダーの香りはひっそりと棚にしまわれている、オリジナルとは
また別の物語です。かといって単にタイムリープという要素を借りただけではなく、
ちゃんとこれ以上にないくらい「時かけ」になっている。
「本当の意味での2代目の
」という原作者による形容がまさにその通りと感じました。
それだけでなく、この40年の間に『時をかける少女』の影響を受けて
書かれた数々の名作を逆に受け止めた"集大成"としても作られているように見えたのだけど、
これは深読みしすぎかなあ。
...古文書がそのベールを脱いだ。
かの古文書こそ彼らのコンピュータのOSであり、それに保存された論文集であり、 敵対文明による攻撃を受け滅亡した彼らがその文明の進化の集大成を 後世に伝えんとしたものであった。
あなたの使命はこのOSとデータを解読し、なるべく多くの論文を読み出すことである。
id:nushio さんによる要約から引用
この３日間 9th ICFP Programming Contest をやってました。チーム kuma- に参加させてもらってます。 メンバー４人の使った言語をあわせると Ruby,C,C++,D,Java,Perl という感じでした。 この統一性のなさがたまりません。
今年の課題はとにかく物凄く気合いが入ってて、もう感動しまくりでした。 まず独自のマシン語（calloc/free命令がある以外はわりと普通のRISC）で書かれた バイナリが配られてて、それを自分でエミュレータを書いてブート。すると、 UMIX という怪しげなシステムが立ち上がって、そこに転がってるプログラミング言語パズル チックな Task を試行錯誤しながら解いていく…というもの。それぞれのTaskのために UMIX上にこれまた怪しげな言語のインタプリタが何個も用意されてて、もうこれ、 参加者じゃなくて CMU の主催者が優勝でいいよ！とわりと本気で思ってしまうくらい。
古文書 は今でも ダウンロードできるみたい。プログラマな方ならコンテストの勝敗とか 関係なくとも１週間は楽しめる素材だと思います。超おすすめ。
shinichiro.h さんが詳細な感想を書かれてるので、各パズルについてはそちらを参照いただくとして… あ、ADVTRはやってみると意外と手で解けます。ちなみに「もっと悲惨な世界」を抜けると その先に第５の言語処理系が待ちかまえてまして、それが今回色々あったなかで個人的に 一番楽しめた課題なので、ぜひぜひ挑戦してみてください。 （このタスクに関するネタバレを以下にコメントアウト）
nushioさんとこ に バックグラウンドストーリーの素晴らしい要約が。
キミならどう書く2.0 Round 2。 違うのは言語だけな同じ処理をみんなで書いても面白くないので、 Haskellな人は配列とかハッシュ表でメモ化している暇があったら 無限リストで実現する義務があると思うんだ（すごい偏見）！ 私はHaskellな人ではないので知りませんが。
import Maybe
import List
-- まったくもってこれ以上ないくらいごくごく普通の何の変哲もない zipWith
zipWith' :: (a->b->c) -> [a] -> [b] -> [c]
zipWith' f xs ys = f (head xs) (head ys) : zipWith' f (tail xs) (tail ys)
-- g!!n == 自然数(n+1)が収束するまでのステップ数
g :: [Int]
g = 1 : map (+1) (zipWith' fromMaybe m3p1 d2)
where
(_:_:m3p1) = unfoldr (\(x:_:_:xs) -> Just (x,xs)) g
d2 = foldr (\x xs -> Just x:Nothing:xs) [] g
-- h!!n == [1..n+1] の中で、収束にかかるステップ数が最大のもの
h :: [Int]
h = map snd $ scanl1 max $ zip g [1..]
main = print h
[1,2,3,3,3,6,7,7,9,9,9,9,9,9,9,9,9,18,18,18,18,18,18,18,25,25,27,27,27,27,27,27, 27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,54,54,54,54,54,54 ,54,54,54,54,54,54,54,54,54,54,54,54,54,73,73,73,73,73,73,73,73,73,73,73,73,73,7 3,73,73,73,73,73,73,73,73,73,73,97,97,...
おおー綺麗！ そうか、iterate なら zipWith' のようなことをしなくても自然と パターンマッチより外で (:) してくれますね。偶数奇数の振り分けは interleave で 表現できるのも思いつきませんでした…
IsCollection と TypeCast で何が起きているのかぱっと見で 全く掴めなかったので、じっくり読み込みつつ、一般化されてる部分を取っ払って 今回の例に限って自分で書いてみることにしました。
とりあえず、こんな風にソースコード側でオプション指定できるの知らなかった。
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-undecidable-instances #-}
{-# OPTIONS -fallow-overlapping-instances #-}
concatN を作るためには、ある型がリストであるか、そうでないかを判定して場合分けがしたい。 逆に、その場合分けさえできるならば残りを書くのは全く難しくありません。というわけで、 まず、引数型 c がリスト型かどうかを外からYes/Noで渡してもらったと仮定して concatN する 補助関数。
data Yes
data No
class ConcatN yn c a | yn c -> a where
concatN' :: yn -> c -> [a]
instance は以下のように、リストじゃない場合（第一引数がNo型の場合）と、 リストな場合（第一引数がYes型の場合）の２種類。リストだった場合、その リストの要素型がリストかどうかをさらに判定してくれるまじかるな型クラス IsList が存在することにして、それを使っています。
instance ConcatN No a a where
concatN' _ a = [a]
instance (IsList c yn, ConcatN yn c a) => ConcatN Yes [c] a where
concatN' _ = concatMap (concatN' (undefined::yn))
で、これを使えば、ネストしたリストを渡されたら全部flatにする関数は、 簡単にこんな感じで。
concatN :: ConcatN Yes c a => c -> [a]
concatN = concatN' (undefined::Yes)
あとは IsList を書けば完成。直感的には、こう書きたい。
class IsList typ yn | typ -> yn
instance IsList [e] Yes
instance IsList typ No
ところがこれはコンパイラに怒られてしまいます。判定したい型 typ に応じてそれが リストであるかリストでないかは一通りに定まらなければならないのに、この定義だと、 typとしてリスト型（例えば[Bool]）を渡したときに、e=Bool として IsList [e] Yes を 選ぶこともできるし、typ=[Bool] としてIsList type No をインスタンス化することも できてしまう。曖昧ですよエラー。
「複数のinstanceが適合する場合は即エラーにするんじゃなくて、、一番specializeされている ものを選ぶ」という挙動にする拡張が -fallow-overlapping-instances なんだけど、この場合はこれもダメ。というのは、[e] Yes と typ No だと、Yes と No で 完全に具体的な型に特殊化されちゃってて、どっちの方が限定的かという順序がつけられない から。
ここでトリック第１弾。
class IsList typ yn | typ -> yn
instance IsList [e] Yes
instance Equals b No => IsList typ b
Equals は後で定義する、二つの型が一致する場合のみinstanceとなるような型クラスで、 結局、b=No となるのでさっきと意味的には何も変わりません。が、[e] Yes と typ b なら、 かたや[e]にYesと具体化されていて、かたやtypにbとどっちも型変数のまんま。[e] Yes の 方がより特殊化されているので優先度高、と順序がつけられるようになりました。 two-class trick というらしいですよ。
あとはEquals。これは直感的には、こう書きたい。
class Equals a b | a->b, b->a
instance Equals a a
ところが、これは残念ながらうまくいかない。この定義だと、Equals を使っている
instance Equals b No => IsList typ b
のところで、Functional Depedency の情報を使うと、実際にIsListが使われる以前に b は No 型でなければならないことが一意に確定してしまって、（実際、確定したその情報自体は 実に正しいのだけれど）、型システムとしては、原理的には（条件を満たす）任意の型で instance 化できなきゃいけないはずのbという型変数と具体的な型 No とを同一化することは できないので、エラーにしてしまう、らしい。 （実はここがエラーになる必然性がまだよくわからないんですけど…）
ここでトリック第２弾。 [PDF] の最終ページに解説あり。
class IsList typ yn | typ -> yn
instance IsList [e] Yes
instance Equals' () b No => IsList typ b
class Equals' t a b | t a -> b, t b -> a
instance Equals'' t a b => Equals' t a b
class Equals'' t a b | t a -> b, t b -> a
instance Equals'' () a a
１個むだなパラメータ t を増やす。そして、１回意味なさげなforwardを入れる。 最終的に結局二つの型が一致する場合だけinstanceとなる定義になっているので 意味は一緒なんですが、これで型チェッカをなだめることが可能になります。何故か。 ghcの実装がそうなのか型システムの定義がそうなのかよくわからんのですが、
instance Equals' () b No => IsList typ b
に関して上で書いたようなチェックをするときは Equals' の instance 宣言のheadまでしか 見に行かないようで、
instance Equals'' t a b => Equals' t a b
この Equals' t a b からは「a=b である」という制約は出てこないので、何も問題には なりません。さらに、↑この instance 宣言自体をチェックするときは、ここだけ見ている 限りでは t が () とは限らないので、Equals'' t a b => が
instance Equals'' () a a
これとマッチするとは断定できない。ので、このinstanceを使ってaとbを同一化しようとして エラー…にはならない。単になんにもチェックされずにスルー。というわけで無事に コンパイルが通ります。
という感じかなーと思ったのですけど、Equals の実装はやっぱりまだよくわかってないです。
のかな。Functional Dependency が型チェック/型推論のどこに影響するのかわかってないので わかれてないだけな気がしてきました。 とりあえず無駄に１回forwardしておくとうまく行くというのは BOOST_PP_CAT の実装を思い出しましたが、それとは全然違う理由っぽいことだけなんとなく把握。
最後に、全部つなげたもの。
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-undecidable-instances #-}
{-# OPTIONS -fallow-overlapping-instances #-}
data Yes
data No
class ConcatN yn c a | yn c -> a where
concatN' :: yn -> c -> [a]
instance ConcatN No a a where
concatN' _ a = [a]
instance (IsList c yn, ConcatN yn c a) => ConcatN Yes [c] a where
concatN' _ = concatMap (concatN' (undefined::yn))
concatN :: ConcatN Yes c a => c -> [a]
concatN = concatN' (undefined::Yes)
class IsList typ yn | typ -> yn
instance IsList [e] Yes
instance Equals' () b No => IsList typ b
class Equals' t a b | t a -> b, t b -> a
instance Equals'' t a b => Equals' t a b
class Equals'' t a b | t a -> b, t b -> a
instance Equals'' () a a
test1 = concatN [[[True]],[[False,True]],[]]
test2 = concatN [[1::Int,2,3],[4]]
test3 = concatN [[[Just True]],[[Just False, Just True]],[]]
あーあと、そもそもの始まりとして、いきなり instance の specialization で リストかどうかを区別してconcatNを書き始めずに一旦 IsList で Yes/No を経由するのは、 引数の型から返値の型をFunctional Dependencyを使って推論させられるようにするため かな。そうでないと、前回の私のやつ みたいに 返値の型を手で書いてやらないといけなくなるんじゃないかと。
