February 1, 2008
IT戦士amachangのこのエントリーを見てJavaScriptで無限リストをやってみたくなった。amachangのやりたいことをあんまり理解してないので，関係ないかも知れないけど…。
無限リストは先頭要素の値と，n番目の要素の値からn+1番目の要素を計算する関数の組で表現できる。
JSにはタプルはないので，配列でこの組を保持することにして1から始まる自然数の無限列は次のような感じになる。
var nat = [1, function (x) { return x + 1; }];
このnatという無限列の10番目を取り出すには
function next(n) {
return [n[1](n[0]), n[1]];
}
function pos(ix, n) {
for (var i=0;i<ix;i++) {
n = next(n);
}
return n[0];
}
こんな感じのpos関数を作っといて
print(pos(9, nat)); // 10
とかやればいい。
調子にのってHaskellのtakeやmap風のこともやってみる。
function take(n, inflist) {
var ary = [];
for (var i=0;i<n;i++) {
ary.push(inflist[0]);
inflist = next(inflist);
}
return ary;
}
function map(func, inflist) {
var n = inflist;
return [func(n[0]),
function(x) {
n = next(n);
return func(n[0]);
}];
}
var evens = map (function(x) { return x*2; }, nat);
print(take(10, nat)); // 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
print(take(10, evens)); // 2, 4, 6, 8, 10, 12, 14, 16, 18, 20
素数の列を
var prime = [2, function (prime) {
prime++;
outloop:
while(true) {
for(var i=2;i<=Math.sqrt(prime);i++) {
if (prime % i == 0) {
prime++;
continue outloop;
}
}
return prime;
}
}];
と作っておけば，
print(pos(99, prime)); // 541 (100番目の素数) print(take(100, prime)); // 100個まで素数を列挙
みたいな感じで遊べる。
プログラミング in OCamlっていう本を参考にしているので，考え方はOCaml風(?)．もっとJavaScript風の書き方がありそうだなぁ。
February 2, 2008
amachangさんが試行錯誤しているのを見て，ついかっとなってやってしまった。
少し長いけど，ようするにフィボナッチ数列をHaskell風に
cons(0, cons(1, zipWith(add, fib, cdr(fib))))
と書きたかった。
以下が実装。
(* 16:00 修正: ひろきのだいちくんの指摘により，selfだったところをidentityに変えました。 ついでに，使ってなかった関数を消してすっきりさせました。*)
function Cons (car, cdr) {
if (car == null || cdr == null) {
throw "illegal object.";
}
this.car = car;
this.cdr = cdr;
}
function Action (act) {
if (act == null || !(act instanceof Function)) {
throw "illegal object.";
}
this.action = act;
}
function Thunk (any) {
if (any instanceof Thunk) {
this.value = any.value;
this.evaled = any.evaled;
} else {
this.value = any;
this.evaled = !(any instanceof Action);
}
}
var _ = function (f) { return new Thunk(f); };
var action = function (f) { return _(new Action(f)); };
var nil = function () { };
var identity = function () { return this; };
Cons.prototype.run = identity;
Number.prototype.run = identity;
String.prototype.run = identity;
Boolean.prototype.run = identity;
Function.prototype.run = identity;
nil.run = identity;
nil.toString = function () { return "nil";};
Action.prototype.run = function () {
return this.action();
};
Thunk.prototype.run = function () {
if (this.evaled) {
return this.value;
}
this.value = this.value.run();
while (this.value instanceof Thunk) {
this.value = this.value.run();
}
this.evaled = true;
return this.value;
};
Thunk.prototype.toString = function () {
return this.run().toString();
};
Cons.prototype.toString = function () {
var str = "(";
var car = this.car.run();
var cdr = this.cdr.run();
while (cdr instanceof Cons) {
str += (car == nil) ? "" : car;
car = cdr.car.run();
cdr = cdr.cdr.run();
if (car != nil) str += " ";
}
str += ((car == nil) ? "" : car);
str += ((cdr == nil) ? "" : " . " + cdr);
return str + ")";
}
/*** premitives ***/
function cons (car, cdr) {
return action(function () { return new Cons(car, cdr) });
}
function car (val) {
return action(function () {
val = val.run();
if (val == nil) {
return nil;
}
if (!(val instanceof Cons)) {
throw "cons applyed to non-Cons object.";
}
return val.car;
});
}
function cdr (val) {
return action(function () {
val = val.run();
if (val == nil) {
return nil;
}
if (!(val instanceof Cons)) {
throw "cons applyed to non-Cons object.";
}
return val.cdr;
});
}
/*** operators ***/
function decr (n) {
return action(function () {
n = n.run() - 1;
return n;
});
}
function incr (n) {
return action(function () {
n = n.run() + 1;
return n;
});
}
/*** list ***/
function nth (n, xs) {
return action(function () {
if (n.run() <= 0) {
return car(xs);
}
return nth(decr(n), cdr(xs));
});
}
function dup (lst) {
return action(function () {
if (lst.run() == nil) {
return nil;
}
return cons(car(lst), dup(cdr(lst)));
});
}
function append (xs, ys) {
return action(function () {
if (xs.run() == nil) {
return dup(ys);
}
return cons(car(xs), append(cdr(xs), ys));
});
}
function take (n, lst) {
return action(function () {
if (lst.run() == nil || n.run() == 0) {
return nil;
}
return cons(car(lst), take(decr(n), cdr(lst)));
});
}
function zipWith (op, xs, ys) {
return action(function () {
if (xs.run() == nil || ys.run() == nil) {
return nil;
}
return cons(op.run()(car(xs).run(), car(ys).run()),
zipWith(op, cdr(xs), cdr(ys)));
});
}
/*** infinity ***/
function cycle (lst) {
return action(function () {
return append(lst, cycle(lst));
});
}
function from (n) {
return action(function () {
return cons(n, from(incr(n)));
});
}
ここまで作れば後は
var fib = action(function () {
var add = function (x, y) { return x + y; };
return cons(0, cons(1, zipWith(add, fib, cdr(fib))));
});
でフィボナッチの無限リストが!!
というわけで実行してみる。
print(take(10, cycle(cons(1,cons(2,nil))))); // (1 2 1 2 1 2 1 2 1 2) print(take(10, from(3))); // (3 4 5 6 7 8 9 10 11 12) print(take(10, fib)); // (0 1 1 2 3 5 8 13 21 34) print(nth(99, fib)); // 218922995834555200000
あってるかどうかわからんけど，これやるのに一晩かかったので解説は後日気が向いたら…。
February 2, 2008
一個前のエントリーの続き。
ひろきのだいちくんの例を見てから，改めて自分の例についてちょっと考えた．
n番目からn+1番目を作る関数が引数としてn番目の値しか受け取れなくて，フィボナッチとか書きたいときに，なんかスマートじゃない。
次の値を計算する関数が，値と一緒にさらに次の値を計算する関数を返せばいい。てか参考にした本
では最初からそうなってた（爆
自然数の場合は現在の値から次の値を作り出すには常に1を足すだけでよいから簡単。
var nat = [1, function (x) { return [x + 1, arguments.callee]; }];
フィボナッチだと次の値を作り出すために，現在の値とひとつ前の値が必要なので少し複雑。
var fib = [0, function (x) {
var succ = function (x) {
return function(y) {
return [x+y, succ(y)];
};
};
return [x+1, succ(x)];
}];
で，pos, take, mapはこんな感じか。
function next(n) {
return n[1](n[0]);;
}
function pos(ix, n) {
for (var i=0;i<ix;i++) {
n = next(n);
}
return n[0];
}
function take(n, inflist) {
var ary = [];
for (var i=0;i<n;i++) {
ary.push(inflist[0]);
inflist = next(inflist);
}
return ary;
}
function map(func, n) {
var succ = function (n) {
return function (_) {
n = next(n);
return [func(n[0]), succ(n)];
};
};
return [func(n[0]), succ(n)];
}
実行してみる。
print(take(10, fib)); //0,1,1,2,3,5,8,13,21,34 print(pos(99, fib)); // 218922995834555200000
結局全然JavaScript風じゃないっていう。
元のamachangのエントリーの弾さんのコメントの意味が全然わからないよぅ（汗
February 3, 2008
via. 日本野望の会ブログ: http://www.yabooo.org/archives/60
「3の倍数と3の付く数字だけアホになり、8の倍数だけ気持ち良くなります」
というやつ。
Haskellで剰余も文字列マッチも使わずにやってみた。
import Data.List
mul_of_3 = cycle [False, False, True]
mul_of_8 = cycle [False, False, False, False, False, False, False, True]
include_3 = iter ([False, False, True] ++ (replicate 7 False)) 1
where
expand = concatMap (replicate 10)
iter bs n = let rest = drop n $ iter (expand bs) (n*10)
in bs ++ (zipWith (||) (cycle bs) rest)
merge x y z n = show n ++
(if x || y then "~~~" else "") ++
(if z then "ooOOo" else "")
nabeatsu = zipWith4 merge include_3 mul_of_3 mul_of_8 [1..]
main = mapM_ putStrLn $ take 40 nabeatsu
ghcじゃ日本語リテラル使えないorz
February 12, 2008
またしても野望の会ブログに反応してみる。
http://www.yabooo.org/archives/53
JavaScriptではC++やJavaと違ってprivateなインスタンス変数や，メソッドが定義できないのでなんとかしましょうという話。
同じようなことがPerlでもやられていて，Perl Hacksでは裏返しオブジェクトというのが紹介されています。上記のエントリーと同じ発想で，クロージャを使うわけですがオブジェクトの保存場所が微妙に違います。JavaScriptでやるとこんな感じ？
var Class = {
'create': function (tmpl) {
var repos = [];
var klass = function () {
this._id = repos.length;
repos.push({});
tmpl.initialize.apply(repos[this._id], arguments);
};
for (var i in tmpl) {
if (i == 'initialize') continue;
if (typeof tmpl[i] == 'function')
klass.prototype[i] = function () {
return tmpl[i].apply(repos[this._id], arguments);
};
}
klass.extend = function (obj) {
for (var i in obj) {
klass.prototype[i] = function () {
return obj[i].apply(repos[this._id], arguments);
};
}
};
return klass;
}
};
var Foo = Class.create({
'initialize' : function () {
this.x = 100;
},
'getX' : function () {
return this.x;
}
});
var foo = new Foo;
print(foo.getX()); // 100
print(foo.x); // undefined
メソッドは全部パブリックだし，いろいろ手抜きだけどとりあえず隠蔽はできてます。クラスのコンストラクタそのものをクロージャにしてしまうとこがポイントですね。
メソッドはprototype経由で呼び出されるので，オブジェクトをnewする度に発生する，メモリ消費のオーバヘッドもありません（たぶん
さらに，あとからメソッドを追加したくなった場合は
Foo.extend({
'printX' : function () {
print(this.x);
}
});
foo.printX(); // 100
とかできて，うれしい気持ち…。
February 15, 2008
テスト用のコードでA.pm, B.pm, C.pmとか作っていろいろやっていたら，どうも挙動がおかしい。
で小一時間悩んで思い出した。Bモジュールって標準モジュールに同名のやつがいる!!
