同じパターン変数による同値判定
各言語で試した結果は以下のとおり
Erlangの場合
できる
> case [1,1,1] of [X,X,X] -> "same"; _ -> "different" end. "same" > case [1,1,2] of [X,X,X] -> "same"; _ -> "different" end. "different"
Pureの場合
できる
> case [1,1,1] of [x,x,x] = "same"; _ = "different" end; "same" > case [1,1,2] of [x,x,x] = "same"; _ = "different" end; "different"
Prologの場合
できる
?- [1,1,1] = [X,X,X], write(same); write(different). same X = 1. ?- [1,1,2] = [X,X,X], write(same); write(different). different true.
Haskellの場合
ガード(|)が必要
Prelude> case [1,1,1] of {[x,x,x] -> "same"; _ -> "different"}
Conflicting definitions for `x'
In a case alternative
Prelude> case [1,1,1] of {[x,y,z] | x==y && x==z -> "same"; _ -> "different"}
"same"
Prelude> case [1,1,2] of {[x,y,z] | x==y && x==z -> "same"; _ -> "different"}
"different"
OCamlの場合
ガード(when)が必要
なお(|)は他の言語での(;)と同じ
# match [1,1,1] with [x,x,x] -> "same" | _ -> "different";; Error: Variable x is bound several times in this matching # match [1,1,1] with [x,y,z] when x==y && x==z -> "same" | _ -> "different";; - : string = "same" # match [1,1,2] with [x,y,z] when x==y && x==z -> "same" | _ -> "different";; - : string = "different"
Scalaの場合
ガード(if)が必要
scala> List(1,1,1) match {case List(x,x,x) => "same" case _ => "different"}
<console>:5: error: x is already defined as value x
scala> List(1,1,1) match {case List(x,y,z) if x==y && x==z > "same" case _ => "different"}
res: java.lang.String = same
scala> List(1,1,2) match {case List(x,y,z) if x==y && x==z > "same" case _ => "different"}
res: java.lang.String = different
Gauche(util.match)の場合
述語パターン(? ...)が必要だが、述語パターン中でxを参照できないのがつらい。
苦し紛れに(apply =)を使ったが、もっと複雑な構造とマッチさせるときは使えない。
gosh> (use util.match) gosh> (match '(1 1 1) ((x y z) "same") (_ "different")) *** ERROR: Compile Error: duplicate variable in pattern ((x x x) "same") gosh> (match '(1 1 1) ((x (? (pa$ = x)) (? (pa$ = x))) "same") (_ "different")) *** ERROR: unbound variable: x gosh> (match '(1 1 1) ((? (pa$ apply =)) "same") (_ "different")) "same" gosh> (match '(1 1 2) ((? (pa$ apply =)) "same") (_ "different")) "different"
追記
こういうときは失敗継続が使える
gosh> (match '(1 1 1) ((x y z) (=> k) (if (= x y z) "same" (k))) (_ "different")) "same" gosh> (match '(1 1 2) ((x y z) (=> k) (if (= x y z) "same" (k))) (_ "different")) "different"
節が (pat (=> identifier) body …)の形式である場合、identifier は clause の失敗継続に束縛されます。これは引数をもたない手続きで、呼ばれると、あたかも、 pat の照合に失敗したかの如くマッチャーに戻り、match が残りの節について試行を続けます。それゆえ、body … 内部で追加のテストを実行することが可能で、もし、満足いくものでなければ、 (identifier) を呼ぶことで、照合結果を拒絶することができます。
http://practical-scheme.net/gauche/man/gauche-refj_164.html
再帰定義でないYコンビネータ
Haskellで出来なかったことをPureでリベンジその2
再帰を使わずにYコンビネータを定義する
404 Blog Not Found:Y combinator is forbidden in Haskell!?
ところがぎっちょんぎっちょんちょん。これが出来ないのです。ch_y = \ f -> (\ x -> f (x x)) (\ x -> f (x x))http://blog.livedoor.jp/dankogai/archives/50463152.html
とりあえずそのまま書いてみる。
> y f = (\x -> f (x x)) (\x -> f (x x)); > fact0 f n = if n==0 then 1 else n*f(n-1); > y fact0 4;
しかし、unknown software exceptionで落ちる。
そこで、後ろの項に遅延評価させるための&を追加。
> y f = (\x -> f (x x)) (\x -> f (x x)&); > fact0 f n = if n==0 then 1 else n*f(n-1); > y fact0 4; 24
できた。
ちなみに、組み込みのfixはHaskellと同じく再帰で定義してた。
> show fix fix f = f (fix f&);
チャーチ数の引き算
Haskell風の文法だけど動的型なPureという言語を発見。
The Pure Programming Language
http://pure-lang.sourceforge.net/
Pure has a modern syntax featuring curried function applications, lexical closures and equational definitions with pattern matching, and thus is somewhat similar to languages of the Haskell and ML variety. But Pure is also a very dynamic language, and is more like Lisp in this respect.
というわけで、Haskellでは型エラーで実行出来なかったチャーチ数の引き算をPureでやってみる。
ソースコード
num n = n (+1) 0; inc n f x = f (n f x); zero f x = x; one = inc zero; two = inc one; three = inc two; add m n f x = m f (n f x); mul m n f = m (n f); pow m n = n m; True x y = x; False x y = y; cons x y b = b x y; car p = p True; cdr p = p False; zeros = cons zero zero; incs p = cons (cdr p) (inc (cdr p)); dec n = car (n incs zeros); sub m n = n dec m;
実行結果
> num $ dec three; 2 > num $ sub three two; 1
こういうとき動的型言語は自由でいいな。
Prologとリスト内包表記の対応関係
昨日の麻雀の待ちの問題、Prologのコードがほぼ１対１でリスト内包表記に書き換えられるような気がしたのでやってみた。
例えば、Prologでの順子の処理部(１行目)は、Haskellでは２行目のように記述できるはず。
(Prolog) tenpai(Xs, [[X,Y,Z]|Ys]) :- select(X,Xs,R1), Y is X+1, select(Y,R1,R2), Z is X+2, select(Z,R2,R3), tenpai(R3,Ys). (Haskell) tenpai xs = [[x,y,z]:ys | (x,r1)<-sel xs, (y,r2)<-sel r1, y==x+1, (z,r3)<-sel r2, z==x+2, ys<-tenpai r3]
なお、Prologでのselect(X,Xs,Y)に相当する関数を sel xs = [(x,delete x xs)|x<-xs] で用意する前提。
ソースコード
以上をふまえて出来るだけ直訳した全ソースコード
import Data.List
sel xs = [(x,delete x xs)|x<-xs]
tenpai [x] = [[[0,x]]]
tenpai xs = nub $ [[[x,x1],[0,y,z]] | (x,r1)<-sel xs, (x1,[y,z])<-sel r1, x==x1, y<=z, z<=y+2]
++ [sort $ [x,x,x]:ys | (x,r1)<-sel xs, (y,r2)<-sel r1, y==x, (z,r3)<-sel r2, z==x, ys<-tenpai r3]
++ [sort $ [x,y,z]:ys | (x,r1)<-sel xs, (y,r2)<-sel r1, y==x+1, (z,r3)<-sel r2, z==x+2, ys<-tenpai r3]
実行結果
今回は待ちのところを0が入ったリストであらわすことにした
(Haskellのリストは型をそろえないといけないので)
Main> tenpai [1,1,2,2,3,3,5,5,5,6,7,9,9] [[[0,6,7],[1,2,3],[1,2,3],[5,5,5],[9,9]], [[0,9,9],[1,2,3],[1,2,3],[5,5],[5,6,7]], [[0,5,5],[1,2,3],[1,2,3],[5,6,7],[9,9]]]
おまけ
直訳をはなれて、少しシンプルにしてみたバージョン
import Data.List
del x xs = if length xs == length((xs\\x)++x) then xs\\x else []
tenpai [x] = [[[0,x]]]
tenpai xs = nub $ [[[x,x],[0,y,z]] | x<-xs, [y,z]<-[del [x,x] xs], y<=z, z<=y+2]
++ [sort $ [x,x,x ]:ys | x<-xs, ys<-tenpai $ del [x,x,x ] xs]
++ [sort $ [x..x+2]:ys | x<-xs, ys<-tenpai $ del [x..x+2] xs]
あなたのスキルで飯は食えるか２
麻雀の手牌が入力として与えられたとき、「待ち」を出力するプログラムを書いてください。
http://www.itmedia.co.jp/enterprise/articles/1004/03/news002_2.html
1122335556799 :
“99”をアタマの両面か“55”“99”のシャボであるので、(123)(123)(555)(99)[67]、(123)(123)(55)(567)[99]、(123)(123)(99)(567)[55]が正解です。
SWI-Prologで再挑戦。
ソースコード
外部からpermutationの出力をくわすかわりに内部でselectを使うようにした。
各行の意味は前回とほぼ同じ。
tenpai([X],[x(X)]). tenpai(Xs,[[X,X],x(Y,Z)]) :- select(X,Xs,R1), select(X,R1,[Y,Z]), Y=<Z, Z=<Y+2. tenpai(Xs,[[X,X,X]|Ys]) :- select(X,Xs,R1), select(X,R1,R2), select(X,R2,R3), tenpai(R3,Ys). tenpai(Xs,[[X,Y,Z]|Ys]) :- select(X,Xs,R1), Y is X+1, select(Y,R1,R2), Z is X+2, select(Z,R2,R3), tenpai(R3,Ys). test(X,Z) :- tenpai(X,Y), msort(Y,Z). tests(X,Z) :- setof(Y,test(X,Y),Z).
実行結果
待ちのところをx(…)であらわすようにした。
?- tests([1,1,2,2,3,3,5,5,5,6,7,9,9],X).
X = [[[1, 2, 3], [1, 2, 3], [5, 5], [5, 6, 7], x(9, 9)],
[[1, 2, 3], [1, 2, 3], [5, 5, 5], [9, 9], x(6, 7)],
[[1, 2, 3], [1, 2, 3], [5, 6, 7], [9, 9], x(5, 5)]]よし、今回は普通に結果がかえってくる。
おぼえがき
sortは重複排除もする。
純粋にソートだけするときはmsortを使う。
あなたのスキルで飯は食えるか？
http://d.hatena.ne.jp/katona/20100422/p1
こっちに修正版を書きました
麻雀の手牌が入力として与えられたとき、「待ち」を出力するプログラムを書いてください。
http://www.itmedia.co.jp/enterprise/articles/1004/03/news002_2.html
1122335556799 :
“99”をアタマの両面か“55”“99”のシャボであるので、(123)(123)(555)(99)[67]、(123)(123)(55)(567)[99]、(123)(123)(99)(567)[55]が正解です。
SWI-Prologで挑戦してみた。
tenpai([X],[[X]]). %単騎待ち tenpai([X,X,Y,Z],[[X,X],[Y,Z]]) :- Y=<Z, Z=<Y+2. %Zの値が、Yならシャボ、Y+1なら両面or辺張、Y+2なら嵌張待ち tenpai([X,X,X|Xs],[[X,X,X]|Ys]) :- tenpai(Xs,Ys). %刻子あり tenpai([X,Y,Z|Xs],[[X,Y,Z]|Ys]) :- Y=:=X+1, Z=:=X+2, tenpai(Xs,Ys). %順子あり test(X,Z) :- permutation(X,Y), tenpai(Y,Z). tests(X,Z) :- setof(Y,test(X,Y),Z).
実行結果
(見やすいように改行を入れてる)
?- test([1,1,2,2,3,3,5,5,5,6,7,9,9],X). X = [[1, 2, 3], [1, 2, 3], [5, 6, 7], [5, 5], [9, 9]] Yes ?- tests([5,5,5,6,7,9,9],X). X = [ [[5, 5, 5], [9, 9], [6, 7]], [[5, 6, 7], [5, 5], [9, 9]], [[5, 6, 7], [9, 9], [5, 5]]] Yes
さすがに力任せすぎだった。
本番のtests([1,1,2,2,3,3,5,5,5,6,7,9,9],X).のクエリは時間切れで終わらず(笑)。
おぼえがき
「以下」は、<=ではなくて、=<を使うので注意。
「以上」は、普通の言語と同じで>=。
setofはbagofの結果をソートして重複排除する。
SWI-Prolog では解の表示が省略されたときは w を押すと全部表示してくれる。
演繹定理とコンビネータ
演繹定理（英: Deduction theorem）とは、数理論理学において、論理式 E から 論理式 F が演繹可能ならば、含意 E → F が証明可能である（すなわち、空集合から演繹可能）、というもの。
http://ja.wikipedia.org/wiki/%E6%BC%94%E7%B9%B9%E5%AE%9A%E7%90%86
公理的命題論理では、公理図式として次のものを使うのが一般的である（ここで、P、Q、R は任意の命題）。
* 公理 1 : P→(Q→P)
* 公理 2 : (P→(Q→R))→( (P→Q)→(P→R) )
* モーダスポネンス : P と P→Q から Q を推論する。
これらから明らかに公理図式 P→P が得られる（命題論理参照）。
カリー・ハワード対応では、上述の演繹メタ定理についての変換過程は、ラムダ計算の項から組合せ論理の項への変換に類似している。ここで、公理1がKコンビネータに対応し、公理2がSコンビネータに対応する。Iコンビネータは公理図式 P→P に対応する。
KコンビネータとSコンビネータの型がそれぞれ公理1,2に対応することをHaskellの型推論で確認する。
Prelude> let k x y = x Prelude> :t k k :: t -> t1 -> t Prelude> let s x y z = x z (y z) Prelude> :t s s :: (t1 -> t -> t2) -> (t1 -> t) -> t1 -> t2
->は右結合だから括弧を明示的に書くと・・・
k :: t -> (t1 -> t) s :: (t1 -> (t -> t2)) -> ((t1 -> t) -> (t1 -> t2))
おお、ほんとだ。
