Prologが面白い

　大学の２回生の頃に、プログラミング言語の授業で扱った言語が、LispとPrologでした。今時、そんな古典的な言語をと思われるかもしれないが（と いうか思ってたんですが）、授業を受けてみると、当時C言語とC++しか知らなかった私には、もの凄く新鮮で、他の学生との温度差を感じつつ、毎回の授業 が楽しかった思い出があります。
　さて、そんなLispとPrologに、それ以降全く触れる事が無かったんですが、どう書く？.orgでソートするコードの生成のお題が出題され、C++やC#であれこれ考えて、行き詰った時にふと、「これ、Prologなら簡単に書けそう。」と思ったんです。「強力なバックトラック機能があれば、前の状態に戻って―――」とか何とか、思ったんです。
　で、やってみた訳です。久しぶりのPrologを思い出し（覚えなおし）つつ試行錯誤してみました。他の人のPrologの投稿も参考にしたり、組み込み関数調べたり。

http://ja.doukaku.org/comment/3168/

何とか出来ましたが…あれ？バックトラック一切使ってないし、再帰使ってるだけ…な結果で、簡単に書けたとは言えずとも、簡単な書き方で書けたと思います。

　それから、もう水を得た魚で、Prologの未解決問題に挑戦しました（簡単なやつだけw）。いや～、マッチングによる推論というのが何とも面白いです！分かりやすいのを一つ挙げると、仲間はずれの判定で、次のようなもの。

?- classify([1,1,1,1], X).
X = [homo, 1]

?- classify([1,1,2,1], X).
X = [quasi-homo, 1, 2]

?- classify([1,1,2,3], X).
X = [hetero]

ソースコードは下の通り。

classify([X|Xs], [homo, X]) :- delete(Xs, X, []), !.
classify([X|Xs], [quasi-homo, X, Y]) :- delete(Xs, X, [Y]), !.
classify([Y,X|Xs], [quasi-homo, X, Y]) :- delete(Xs, X, []), !.
classify(_, [hetero]).

解説すると、１行目から順に一致を探します。

1. 値Xに続くリストXsから、値Xを削除したリストが空なら　[homo]。
2. 同様にして、要素Yが一つだけ残っていたら　[quasi-homo, X, Y]。
3. 値Y,Xに続くリストXsから、値Xを削除して空なら　[quasi-homo, X, Y]。
4. [hetero]。

第一引数と尾部分がマッチすれば、第二引数が決まってるといった感じです。

覚えたてのPrologで、今度何かパズルを解くプログラムを書きたいと考えてます。

初投稿 PageRankの計算 C++でどう書く？

最近 どう書く？.org への参戦を始めました。
プログラミングのお題が与えられて、「あなたならどう書く？」と、いったとこでしょうか。
今ではすっかり、次のお題がいつ来るのか、気になって気になって...

中には、似たような投稿が既に出てたり、題意に沿わない気がして、投稿を見合わせる事があります。そういったもので、「これは発表したい」と、思うものはこのブログに載せていこうと思います。

第一回目のお題は、PageRankの計算です。
お題では、行列演算ライブラリを使う事とありましたが。外部ライブラリを使わない版をC++で書きました。valarrayを使いたかったんです。それと、お題ではページ番号が１始まりですが、使いやすい０始まりにしてます。

#include <iostream>
#include <vector>
#include <valarray>
#include <algorithm>
using namespace std;

valarray<double> page_rank(const valarray<size_t> link[], size_t n) {
valarray<double> m(0.0, n * n), r(1.0 / n, n), prev(n);

for (size_t i = 0; i < n; i++)
m[valarray<size_t>(n * link[i] + i)] = 1.0 / link[i].size();

do {
prev = r;
for (size_t i = 0; i < n; i++)
r[i] = (valarray<double>(m[slice(i * n, n, 1)]) * prev).sum();
} while (valarray<double>(abs(r - prev)).max() > 1e-8);

return r;
}

int main() {
const int N = 7;
int data[N][N] = {
{ 1, 2, 3, 4, 6, -1 },
{ 0, -1 },
{ 0, 1, -1 },
{ 1, 2, 4, -1 },
{ 0, 2, 3, 5, -1 },
{ 0, 4, -1 },
{ 4, -1 }};
valarray<size_t> link[N];

for (size_t i = 0; i < N; i++) {
vector<size_t> v(data[i], find(data[i], data[i] + N, -1));
link[i].resize(v.size());
link[i] = valarray<size_t>(&v[0], v.size());
}

valarray<double> rank = page_rank(link, N);
for (size_t i = 0; i < rank.size(); i++)
cout << ' ' << rank[i];
cout << endl;

return 0;
}

== 出力 ==
0.303514 0.166134 0.140575 0.105431 0.178914 0.0447284 0.0607029

なかなか、書き方もややこしいですが、複雑な行列計算をこれだけの量で書けました。
実際のPageRank計算では規模が全く違うので、このコードじゃダメなんでしょうけど、充分楽しめました。