prolog

制御構造まとめ

>と','や;の挙動が全然分かっていなかったので調べてみた。 true, fail, ! 述語 用例 動作 true/0 true 必ず成功する fail/0 fail 必ず失敗する(強制的にバックトレースを行う) !/0(カット) ! 必ず成功する。副作用としてカット以前にバックトレースできなく…

project euler problem 10 answer

区間ふるいを使ったらとけた。ひどいソース。 primes(Primes, Prime, NextPrimes) :- [Prime, _] = Primes, primes_next(Primes, NextPrimes). primes_next([Prime, [Head, Appender]], NextPrimes) :- P1 is Prime + 1, (primes_is_prime(P1, Head, Appende…

project euler problem 10 answer ?

32bitのCPUでSWI-Prologを動かした場合local stackの上限が128MByteに設定されてしまっているため、以下のプログラムではオーバーフローを起こして動作しない。が、その制限を除けば正しいプログラムだと思う。何とかしたい! primes_new(Primes) :- Primes …

project euler problem 9 answer

良心に苛まれながらも貼る。 SICPにも似たような問題があった。SWI-Prologでグローバルスタックを拡張して実行した。 % ペアを作る(おまけ) integer_pairs_new(PairSeed) :- PairSeed = [[[1, 1] | Tail], Tail]. integer_pairs(PairSeed, Pair, NextPairSee…

差分リストやループ

Prologで差分リストや末尾再帰の述語を書く場合、たいてい以下のようなイデオムを利用する。 差分リスト % たどる diff_list(List, ResultList) :- diff_list_sub(List, [ResultList, []]). diff_list_sub([Head | Rest], [Result, Tail]) :- <Headを何かしてXにする> [Result, Appe</headを何かしてxにする>…

project euler problem 8 answer

最近、ブログに回答を書くのがマナー違反なんじゃないかと思えて来た。 take(N, [Lcar | Lcdr], [Lcar | R]) :- N > 0, N1 is N - 1, take(N1, Lcdr, R). take(0, _, []). % 数字のアトムを数値に変換 numeric_to_number(List, NumberList) :- numeric_to_nu…

project euler problem 6-7 answer

解いた。5は手で解いてしまったので飛ばす。 sum_sub(N, M, Acc, Sum) :- N1 is N + 1, Acc1 is N + Acc, sum_sub(N1, M, Acc1, Sum). square_sum(N, M, Sum) :- square_sum_sub(N, M, 0, Sum). square_sum_sub(M, M, Acc, Sum) :- Sum is Acc + M * M. squa…

project euler problem 4 answer

二時間くらいかかっているorz 戦略は大きいほうから順に回文数を探し、因子を探していくというもの。ごく普通のもの。 split_at(N, [Lcar | Lcdr], [Lcar | F], R) :- N > 0, N1 is N - 1, split_at(N1, Lcdr, F, R), !. split_at(_, [], [], []). split_at(…

isと=

違いを理解していなくてはまった。Aとaを関連付けしたかった。でもこれはできない | ?- A is a, B is A. A is a, B is A. uncaught exception: error(type_error(evaluable,a/0),(is)/2) | ?- こういう、atomを関連付ける場合は=を利用する。 | ?- A = a, B …

project euler problem 1-3 answer

練習がてら解いてみた。 回答 デフォルトのGnu PrologだとProblem3は速攻でヒープが足らなくなって落ちる。面倒なのでSWI-Prologを利用した。 problem1(N, Result) :- N1 is N - 1, problem1_sub(N1, Result, 0), !. problem1_sub(0, Acc, Acc). problem1_su…

差分リストの練習 その4

split_at_right。Prologで作る数学の世界―Prologそして集合‐位相‐群の第五章の問題の回答でもある。バックトラックを利用したもので、Nが小さい場合は効率がよい。現時点で一番prologらしいプログラム。 split_at_right(N, List, Left, Right) :- right_sub(…

剰余

Prologで作る数学の世界―Prologそして集合‐位相‐群の第4章の問題。余りを求めろ。 abs(A, B) :- A > 0 -> B is A ; B is -A. % 条件は % A = B * Q + R, 0 <= R < abs(B) % 割る数の絶対値よりも余りが小さい res_q(A = B*Q + R) :- abs(B, B1), Q1 is A //…

PI

Prologで作る数学の世界―Prologそして集合‐位相‐群の第3章の問題。arctanを定義してπの近似値を求めろ。最初に書いた効率の悪いやつもつけて % 普通の再帰 atn(X, N, Sum) :- N > 0, (N mod 2 =:= 1 -> Sum1 is X ** (N * 2 - 1) / (N * 2 - 1) ; Sum1 is -…

fizzbuzz

僕のprolog力を精一杯使って解いた! fizzbuzz(N) :- fizzbuzz_sub(1, N). fizzbuzz_sub(Current, Max) :- Current > Max, !. fizzbuzz_sub(Current, Max) :- (Current mod 15 =:= 0 -> write('fizzbuzz'); Current mod 3 =:= 0 -> write('fizz'); Current m…

ニュートン法で平方根

Prologで作る数学の世界―Prologそして集合‐位相‐群の第3章の問題。ニュートン法で平方根を求めろ。 newton(N,R) :- newton_sub(N, N, R), !. newton_sub(N, Xn, Xn) :- Xn ** 2 - N < 0.00000001. newton_sub(N, Xn, R) :- Xn1 is Xn - ((Xn ** 2 - N) /(2 …

差分リストの練習 その3

差分リストといいつつ、lastはただのリストの練習だった。 last my_last([_, Head | Rest], Result) :- my_last([Head | Rest], Result). my_last([Result | []], Result). slices split_at(N, [Lcar | Lcdr], [Lcar | F], R) :- N > 0, N1 is N - 1, split_…

差分リストの練習 その2

同期同士の勉強会でお題をもらった! zip list_heads(Lists, Hs, Rs) :- list_heads_sub(Lists, Hs, Rs), !. list_heads(_, [], []). list_heads_sub([[H | R] | Ls], [H | Hs], [R | Rs]) :- H \== [], list_heads_sub(Ls, Hs, Rs). list_heads_sub(_, [], …

差分リストの練習

取り合えずいくつか無理やり差分リストで書いてみる。 % 深さ優先で左から走査する場合 flatten(NestedList, FlatList) :- flatten_sub(NestedList, [FlatList, []]). flatten_sub([X | Xs], [Head , Tail]) :- flatten_sub(X, [Head, Appender]), flatten_s…

差分リストの続き

とりあえず、こんなのが差分リストの定石だということはわかった。 hoge([W | Ws], [Xs, Ys]) :- hoge(W, [Xs, Xs1]), hoge(Ws, [Xs1, Ys]). こういう条件がたくさん登場する。 だめだ ぜんぜん差分リストわからん。10分くらいしか考えてないけど。 とりあえ…

リストと繰り返しのつづき

繰り返し repeatを使った繰り返し。repeatは、自分までバックトラックが達したら再度repeatの次からやり直させる演算子。入力をうけとり、そのまま返したいなら次のようにする。 my_echo :- repeat, get_char(user_input, C), put_char(user_output, C), C =…

カット

バックトラックを禁止する述語らしい。これを使えば リスト - 放牧日記のtakeやdropも my_take(0, _, []) :- !. my_take(N, [Lcar | Lcdr], [Lcar | R]) :- N > 0, N1 is N - 1, my_take(N1, Lcdr, R). my_drop(0, L, L) :- !. my_drop(N, [_ | Lcdr], R) :-…

リスト

prologのリストのリテラル表記。 [this, is, a, list]. リストはLISPと同じようなセルになっている。 [Car | Cdr] これはyes。LISPのリストとまったく一緒。 | ?- [a | [b | [c | []]]] = [a, b, c]. take appendは昨日やったので、takeなどを定義してみた。…

規則の読み込みのメモ

ファイルを読み込ませる以外の方法。ファイルから読み込ませる場合はこうする。 | ?- ['filename.pl']. ファイル全体ではなく一部の分のみ読み込ませる場合、[user].でいける。 | ?- [user]. {compiling user for byte code...} even(0). even(s(s(X))):- ev…

家系図

とりあえず、prologでは家系図を作ってみるのが定石らしい。 ので、華麗なる一族 (競馬) - Wikipediaことマイリー系を作ってみる。 あまり大きいのは辛いので、ここで断念。 /* -*- mode: prolog -*- * horse-family.pl */ /* 牝馬 */ female(mairie). % マ…

prolog-mode

設定が間違っていた。prolog.elは/usr/share/emacs/site-lisp/prolog-el/prolog.el にあって、こっちを利用する。.emacsは以下のとおり。 (autoload 'run-prolog "prolog" "Start a Prolog sub-process." t) (autoload 'prolog-mode "prolog" "Major mode fo…

append

insertを参考にappendを書いた。とりあえず動くように見える。 insert(1, X, L, [X | L]). insert(N, X, [Y | L], [Y | Z]) :- N > 1, N1 is N - 1, insert(N1, X, L, Z). my_append([], S, S). my_append([Fcar | Fcdr], S, [Fcar | R]) :- my_append(Fcdr,…

prologをやるぞー

なんかprologをやることになった。 参考 Prolog with GnuEmacs M.Hiroi's Home Page / Prolog Programming 環境 とりあえず、環境を作らなければ話にならないので処理系をインストール。 ubuntu 7.10でprologを検索すると、これだけ出てくる。 UBUNTU-VM [0]…