それPrologでできたよ
生まれてはじめてprologをまともにいじった気がする。
http://hiratch.net/blog/archives/2007/01/000146.html に 「prologとは違うの？」とはてブコメントつけたら、
できねーじゃん! (ﾉ｀Д´)ノ彡 ┻━┻ あれか、算術演算は順方向にしか計算できないようになってるってことか。
ということになったので、逆もいける階乗をProlog上で書いてみた。
まず、「算術演算は順方向にしか計算できない」というのは「is の計算に方向性があるからです」ということらしい *1 *2。
じゃあ、っていうんでパターンマッチ(バックトラック？)が効くように自然数をベタに定義(nat)した上で、足し算とかけ算(nplus,times)も定義*3。で、その自然数上の階乗を定義(nfact)してから、変換をかまして数値上の階乗(fact)も定義。ソースは以下。
nat(0). nat(s(X)) :- nat(X). nplus(0, Y, Y). nplus(s(X), Y, s(Z)) :- nplus(X, Y, Z). times(0, _, 0). times(s(X), Y, Z) :- times(X, Y, Z1), nplus(Z1, Y, Z). nfact(0,s(0)). nfact(X,Sum) :- nplus(X1,s(0),X), nfact(X1,Sum1), times(Sum1,X,Sum). t(0,0). t(s(X),N) :- t(X,N1), N is N1 + 1. fact(X,Y) :- t(SX,X), nfact(SX,SY), t(SY,Y).
で、こうなる。
Welcome to SWI-Prolog (Multi-threaded, Version 5.2.13) Copyright (c) 1990-2003 University of Amsterdam. SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software, and you are welcome to redistribute it under certain conditions. Please visit http://www.swi-prolog.org for details. For help, use ?- help(Topic). or ?- apropos(Word). ?- fact(4,X). X = 24 Yes ?- fact(X,24). X = 4 Yes ?-
勢いで超素朴に自前で作っちゃったけど、逆方向もいける自然数の算術演算って用意されてないのかな。いくらなんでも、これではおもちゃにしか使えない。
お
?- fact(X,Y). X = 0 Y = 1 ; X = 1 Y = 1 ; X = 2 Y = 2 ; X = 3 Y = 6 ; X = 4 Y = 24 ; X = 5 Y = 120 ; X = 6 Y = 720 ; X = 7 Y = 5040 ; X = 8 Y = 40320
こんなんもできた。X=8が出るのに数分かかってしまったのでここで打ち止め。
