■
ゴルフ飽きてきたけど、微妙に、はすけるごるふぁーが増えてきたのは嬉しい。問題は一日一問くらいがいいな。別に律儀に全部やる必要もないが。まあ、Haskellだけはとりあえずやっておくかとか。以下、感想とか、メモとか、一部ネタばれ
問題は詳しくは
http://shinh.org:81/
楽しいのは、smileys triangle、permutaterあたりかな〜。あと意外性でecho。というか、echoできないと、他でも苦しい
トップじゃないやつ：99shinh、example_com、Dance、e、smiley、permutater
まだ縮みそうなやつ：tennis、ボーリング、Hamming numbers、Hole in one、card
・99shinh
99 bottles of beerみたいなやつ。普通に4人中最下位なんだよなorz多分、minimalなのは、systemでPerlかRuby呼んじゃうのだけど、どうなんだろうな〜。systemだったら、どうでもいいんだけど、正攻法で負けてるとなると、どこを1ブロックと見るかの違いかな〜
・example_com
www.example.comに繋いでindex.html取って来いという問題。なんだけど、ネットワーク使えない。これもsystemでperlかruby呼ぶのがminimalなんだろうけど、わかんねー。登録してないけど、現在451B。最下位
・Dancing Kids
102Bでminimalだろうと思ったら、一晩であっさり抜かれたという。systemではないよな〜。import System;main=system""だけで27Bだし。あと2B縮みそうにない
・e
ネイピア数を小数点以下100桁まで求める問題。最初、多倍長整数除算(の一部)を自力で実装して142B。それ、printした方が短いやん！という話。よく考えたらHaskellは多倍長整数があるのだった。とはいえ、46Bってどうなってんだ?
・Hamming numbers
Hamming数は、2^a*3^b*5^c(a,b,c=0..)という形の数らしい。で、これを小さい順に列挙していく問題。Wikipediaにlazyな言語の力を示すのに使われる的なことが書いてあるけど、関係ない気が。上限決まってなければ、filterで、2,3,5以外で割り切れる数を落とせばいいだけだし。ゴルフは上限が決まってるので、別のアルゴリズムの方が短い
・Hole in one
ひたすらだるい。よく頑張ったな自分。抜かれても、やる気しない
以下ネタばれ含む
続きを読むCurry
少しは触っておいた方が理解の助けになるだろうと思ったので、Curryを使ってみた
処理系は、ここに列挙されているものから、ネイティブコンパイラで、かつWindows用のバイナリ(要cygwin?)が配布されてるZinc compilerになりました。一応、Tutorialがあるけど、大したことが書いてないので、さっと目を通してExample codeを読むのがよさげ。というか、ろくな説明が見当たらないので、Haskell知らない人には、敷居が高いんじゃないかと思った。
関数的に書きたいなら、ほぼHaskell感覚で使えるけど、そのへんは略。Haskellと違う部分の一つは非決定性が自然に表れる点。例えば
choose x y = x choose x y = y
という定義があったら、GHCだと、パターンがオーバーラップしてるという旨の警告が出て、実行時には、上の式のみが使われることになるけど、curryでは、両方使われるらしい。インタープリタ上での実行結果はこんな感じに
main> choose 4 5 4 More solutions? [Y(es)/n(o)/a(ll)] y 5
これは自然だとは思う。GHCみたく、定義を書く順序によって、実行結果が変わるというのは本来キモイと思う。ただ、実際には、いくつかのパターンに対する定義を書いて、それ以外のケースでは、という意味で"f _ _ =..."みたいな定義を最後に添えることがあるけど、Curryでは、こういうやり方はまずいということになる。常にパターンが排他的かどうか強く意識しないといけない。例えば、述語版appendだったら
app [] x y = x==y app (x:xs) y (z:zs) = x==z && (app xs y zs) app _ _ _ = False
と書くとまずい。Curryの方が自然ではあるけど、書きやすさではHaskellに分がある気がするなぁ。あとゴルフで不利(どうでもいい
んで、次がNarrowing。簡単な例としては、
main> x++[1,2,3] =:= [1,2,3] where x free
{x = []} Success
More solutions? [Y(es)/n(o)/a(ll)] y
No more solutions(=:=)は、a->a->Successという型らしい。まあ、なんなのかよく分からんが、単一化演算子とかそんな感じかね。"x free"という指定もよく分かってないけど、まあ自由変数という意味なんだろうな。値が未決定な状態の変数というイメージかな〜
いちいち、More solutions?..とか出てくるのがださいので、全ての解を得るには、findallという関数を使えばいいらしい。
main> :t findall (a -> prelude.Success) -> [a] main> findall (\x-> x++[1,2,3] =:= [1,2,3]) [[]]
まあ、面白くない。choose x yの解は
main> findall (\x -> choose 4 5 =:= x) [4,5]
で求まる。あと、
main> findall (\x -> (fst x)++(snd x) =:= [1,2,3]) [([],[1,2,3]),([1],[2,3]),([1,2],[3]),([1,2,3],[])] main> findall (\x -> g x) where g(a,b,c)=a++b++c=:=[1,2,3,4] [([],[],[1,2,3,4]),([],[1],[2,3,4]),([],[1,2],[3,4]),([],[1,2,3],[4]),([],[1,2,3,4],[]), ([1],[],[2,3,4]),([1],[2],[3,4]),([1],[2,3],[4]),([1],[2,3,4],[]),([1,2],[],[3,4]),([1,2],[3], [4]),([1,2],[3,4],[]),([1,2,3],[],[4]),([1,2,3],[4],[]),([1,2,3,4],[],[])]
とかは、論理型っぽいかな〜。
lazyなので、解が無限にあっても、take nとかで適当なとこで打ち切ることができる。例えば、
main> take 10 $ findall (\x -> (fst x)++[1,2,3] =:= (snd x)) [([],[1,2,3]),([_a],[_a,1,2,3]),([_b,_c],[_b,_c,1,2,3]),([_d,_e,_f],[_d,_e,_f,1,2,3]), ([_g,_h,_i,_j],[_g,_h,_i,_j,1,2,3]),([_k,_l,_m,_n,_o],[_k,_l,_m,_n,_o,1,2,3]),([_p,_q,_r ,_s,_t,_u],[_p,_q,_r,_s,_t,_u,1,2,3]),([_v,_w,_x,_y,_z,_a1,_b1],[_v,_w,_x,_y,_z,_a1,_b1, 1,2,3]),([_c1,_d1,_e1,_f1,_g1,_h1,_i1,_j1],[_c1,_d1,_e1,_f1,_g1,_h1,_i1,_j1,1,2,3]),([_k1 ,_l1,_m1,_n1,_o1,_p1,_q1,_r1,_s1],[_k1,_l1,_m1,_n1,_o1,_p1,_q1,_r1,_s1,1,2,3])]
こんなんが解けるのはちょっとびっくりした。
Bool式も解ける
main> findall(\x->(x&&True)=:=True) [True]
あと、制約条件が複数ある場合は、(&)演算子を使う
main> findall(\x -> f x=:= True & g x=:= False) where f(a,b,c)= not a&& b || c;g(a,b,c)=a && b && c [(True,False,True),(False,True,_a),(False,False,True)]
解けない例も山ほどある。数値型はinductiveに定義されてるわけではないので、算術式は基本的に解けない
main> findall(\x -> x+3 =:= 5) Suspended
勿論、data Nat = Z | S Natとか定義して、足し算、掛け算を定義してやればできるけど。findall(\x-> (x++[1,2]==[1,2])=:=True)も解けない。それから当然、Higher-order narrowingもsuspendする
--suspendする data Person = John | Peter | Art deriving (Show) father John = Peter father Peter = Art main = print $ map (\f->f Art) $ findall (\f -> f John =:= Art)
何気に、(=:=)はEqクラスでなくても使えるのだな〜と。純粋に項として比較するのか。要するに、x==y =:= Trueと、x=:=yは一般には違う意味だということかな
慣れれば強力なのかもしれないけど、意外とsuspendが多くて、使いづらい。Prologは、そのへん解けない問題は、そもそも書きにくいようになってるのかな(知らんけど)。まあ、表現力がないとも言えるけど、関数型言語的な表現力を許したので、SLD-resolutionと同程度の探索能力しかないnarrowingでは解けない例が簡単に書けてしまうようになったとか、そんな感じなんだろうか
あと、どうでもいいけど、Listの(\\)の挙動がおかしい。Haskellと引数が逆。まあバグなんだろうけど
