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と引数が逆。まあバグなんだろうけど