application/xhtml+xml の場合 (というより XML の場合)、XPath では namespace を持っているノードに対して prefix が必須 *1。すなわち HTML で //body と書いていたやつは //h:body とする必要があり、さらに h を http://www.w3.org/1999/xhtml (XHTML の NS URI) に関連付ける必要がある。

DOM 3 XPath では prefix の解決に XPathNSResolver というのを使っていて、これで prefix を関連づけてやる。

var context = document;
var resolver = function (prefix) {
    if (prefix == "h") return "http://www.w3.org/1999/xhtml";
    return null; # unknown
};
var expr = document.createExpression("//h:body", resolver);

で、これだと text/html のとき (全てのノードは名前空間が空) h:body はなにも選択しなくなってしまって悲しいので条件分岐する。

var context = document;
var resolver = function (prefix) {
    if (prefix == "h") return (document.documentElement.namespaceURI ? "http://www.w3.org/1999/xhtml" : "");
    return null; # unknown
};
var expr = document.createExpression("//h:body", resolver);

document.documentElement.namespaceURI でドキュメントが XML として扱われているかを判別してよさげなのをかえす。

基本的にはこれで十分だけど、XML として処理されるとき、dc: や rdf: とかもちゃんと選択できると嬉しい。毎回 resolver に条件を追加するのもいいけど、dc とか rdf とか、普通 prefix を変えたりしないので、こうする。

var context = document;
var resolver = function (prefix) {
    var c = document.createNSResolver(context).lookupNamespaceURI(prefix);
    if (c) return c;
    if (prefix == "h") return (document.documentElement.namespaceURI ? "http://www.w3.org/1999/xhtml" : "");
   return null; # unknown
};
var expr = document.createExpression("//h:body", resolver);

createNSResolver は Node をあたえると、そのノードが持っている名前 prefix と URI の対応をつかってリゾルバを作る。下位のノードは上位のノードの prefix/URI マッピングも持っている (というかスコープにある prefix は全部とってくる) ので、できるだけ下位のノードをわたす。

だいたい汎用的に使える resolver になった。ただ、xhtml の接頭辞に h を使うかはいまいち同意がとれないので、lookupNamespaceURI でみつからないなら全部 xhtml として扱うことにする。

var context = document;
var resolver = function (prefix) {
    var c = document.createNSResolver(context).lookupNamespaceURI(prefix);
    if (c) return c;
    return (document.documentElement.namespaceURI ? "http://www.w3.org/1999/xhtml" : "");
};
var expr = document.createExpression("//h:body", resolver);

割と嬉しい resolver になった。

ちなみに、いろいろ調べているうちに Opera の非互換を踏んでしまった。Opera (9.24/9.5) では resolver が "" (空文字列) をかえすと、null を返したときと同じように NAMESPACE_ERR を投げてしまう (Safari や Gecko では名前空間が空ということにしてくれる)。つまり Opera だと全適用のユーザスクリプトで XPath つかうときはページが XML か HTML かで式自体を変えないといけないのでめんどい。とかいうのを IRC でごちゃごちゃ言ってたら Kuruma さんに報告してもらった。ありがとう！

あと XML の仕様では「名前空間に関連づいていないノードの名前空間」の名前が定義されていないみたい。no value (Namespace in XML) とかだったり null namespace (XSLT) だったりする。

引数全部カリー化したい (一回だけじゃなくて)。可変長引数は考慮しない。

Lambda = Proc
class Lambda
	def curry
		s = self
		args = []
		(1...self.arity).inject(lambda {|x| p args; s[*(args+[x])] }) {|r,i|
			lambda {|x|
				args = args + [x]
				r
			}
		}
	end
end

sum = lambda {|x, y, z| x - y + z }.curry
p sum[1][2][3] # 2
p sum[1][2][3] # args が破壊されて失敗

なんかいろいろやってみたけどうまくいかないので eval に逃げ

Lambda = Proc
class Lambda
	def curry
		s = <<-EOS.gsub(/^¥t{3}/, "")
			lambda {|al|
				args = [#{(1...self.arity).inject(""){|r,i|r<<"a#{i}, "}}al]
				ObjectSpace._id2ref(#{self.object_id})[*args]
			}
		EOS
		eval (1...self.arity).inject(s) {|r,i|
			<<-EOS.gsub(/^¥t{4}/, "")
				lambda {|a#{self.arity-1-i+1}|
					#{r}
				}
			EOS
		}
	end
end

sum = lambda {|x, y, z| x - y + z }.curry
p sum[1][2][3] # 2
p (sum1 = sum[1])
p sum1[2][3]
p lambda {|x, y, z, a| x + y + z + a}.curry[1][2][3][4]

class Lambda
	def curry
		s = <<-EOS.gsub(/^\t{3}/, "")
			lambda {|al|
				args = [#{(1...self.arity).inject(""){|r,i|r<<"a#{i}, "}}al]
				self[*args]
			}
		EOS
		instance_eval (1...self.arity).inject(s) {|r,i|
			<<-EOS.gsub(/^\t{4}/, "")
				lambda {|a#{self.arity-1-i+1}|
					#{r}
				}
			EOS
		}
	end
end

そのまま実装してみます。チャーチ数は自然数 n の場合、引数 f をとり、引数 x に対し f を n 回適用する関数を返す高階関数らしいです。

\f x -> x       -- 0
\f x -> f x     -- 1
\f x -> f (f x) -- 2

数としてもどしたいときは

-- cn はチャーチ数
cn (\x -> x + 1) 0

とかやるとたぶん数になります。

class ChurchNumber < Lambda

	# ¥m n f x -> m f (n f x)
	def +(m)
		n = self
		m = m.to_church_number
		ChurchNumber.new {|f|
			lambda {|x|
				m[f][n[f][x]]
			}
		}
	end

	# ¥n f x -> f (n f x)
	def succ
		n = self
		ChurchNumber.new {|f|
			lambda {|x|
				f[n[f][x]]
			}
		}
	end

	def to_i
		self[lambda {|x| x + 1 }][0]
	end

	def coerce(number)
		[number, self.to_i]
	end

	def inspect
		# "#<%s:0x%08x:%d>" % [self.class, self.object_id, self.to_i]
		"#<%s:%d>" % [self.class, self.to_i]
	end

	def to_church_number
		self
	end
end

class Integer
	def to_church_number
		n = self
		ChurchNumber.new {|f|
			lambda {|x|
				(1..n).inject(x) {|r,i| f[r] }
			}
		}
	end
end

p 1.to_church_number      #=> #<ChurchNumber:1>
p 1.to_church_number.succ #=> #<ChurchNumber:2>
p 2 + 1.to_church_number  #=> 3
p 2.to_church_number + 1  #=> #<ChurchNumber:3>

(0..10).each do |i|
	p [i.to_church_number, i.to_church_number.to_i]
end

わかってなくて苦労したけどようはλを \ にして . を -> にすれば Haskell の記法として読めるみたいだ (普通逆なんだろうけど)

Lazy K のプログラムは Input リストを引数にとり、Output リストを出力する関数とみることができます。でもって空の Lazy K プログラムは I として扱われるため (というか何か書くと I の引数として評価されてく) Lazy K での cat は 0 byte になります。(Input をそのまま Output するので I でいい)

Lazy K のリストは Lisp のようにペアのいれこになっていて、一つのペア (X . Y) は (lambda (f) (f X Y))) と表現するらしいです。

Ruby で Lazy K の Input をそのまんま実装すると

def inputlist(l)
	lambda {|f|
		f[(l.first || 256).to_church_number][inputlist(l[1..-1] || [])]
	}
end

il = inputlist([72, 101, 108, 108, 111])
S = lambda {|x, y, z| x[z][y[z]] }.curry
K = lambda {|x, y| x }.curry
I = lambda {|x| x }

car = il[K]    #=> チャーチ数 72 (car il)
cdr = il[S[K]] #=> (cdr il)
cdr[K]         #=> チャーチ数 101 (car (cdr il))

こんな感じになりました。 Lazy K の Input リストは無限リスト (EOF 以降は 256) になっています。

やばいいたい……

function h (str) {
	var t, cur, stack = [cur = document.createElement("div")];
	while (str.length) {
		if (str.indexOf("<") == 0) {
			if (t = str.match(/^\s*<(\/?[^\s>\/]+)([^>]+?)?(\/)?>/)) {
				var tag = t[1], attrs = t[2], isempty = !!t[3];
				if (tag.indexOf("/") == -1) {
					child = document.createElement(tag);
					if (attrs) attrs.replace(/([a-z]+)=(?:'([^']+)'|"([^"]+)")/gi,
						function (m, name, v1, v2) {
							child.setAttribute(name, v1 || v2);
						}
					);
					cur.appendChild(child);
					if (!isempty) {
						stack.push(cur);
						cur = child;
					}
				} else cur = stack.pop();
			} else throw("Parse Error: " + str);
		} else {
			if (t = str.match(/^([^<]+)/)) cur.appendChild(document.createTextNode(t[0]));
		}
		str = str.substring(t[0].length);
	}
	return stack.pop().firstChild;
}

window.onload = function () {
	var t = [
		h("<div><img src='http://mixi.jp/favicon.ico'/>hello<span style='color:red'>!</span></div>"),
		h("<div class='test'/>"),
		h("<div class='test'><ul><li>aa</li></ul></div>"),
		h("<div class='test' style='background: #f00'>hogehoe  aaa</div>")
	];
	for (var i = 0; i < t.length; i++) {
		var e = t[i];
		document.body.appendChild(e);
	}
};

jQuery でふつうに HTML かいて要素生成しはじめると、$N("div", {attr}, [childs]) みたいなのがめんどくさくてしかたないので簡単なパーサ書いて生成するようにした。innerHTML 使えよって感じですね。なんで innerHTML つかわないで書いたんだっけ……

function hi (str) {
	var t = document.createElement("div");
	t.innerHTML = str;
	return t.firstChild;
}

benchmark({
	"pure dom"  : function () {
		for (var i = 0; i < 1000; i++) {
			h("<div><img src='http://mixi.jp/favicon.ico'/>hello<span style='color:red'>!</span></div>");
			h("<div class='test'/>");
			h("<div class='test'><ul><li>aa</li><li>bb</li></ul></div>");
			h("<div class='test' style='background: #f00'>hogehoe  aaa</div>");
		}
	},

	"innerHTML" : function () {
		for (var i = 0; i < 1000; i++) {
			hi("<div><img src='http://mixi.jp/favicon.ico'/>hello<span style='color:red'>!</span></div>");
			hi("<div class='test'/>");
			hi("<div class='test'><ul><li>aa</li><li>bb</li></ul></div>");
			hi("<div class='test' style='background: #f00'>hogehoe  aaa</div>");
		}
	}
});

# GranParadiso A8
preparing ...
let's go!
.
*** pure dom ***
result : 2213.987429[ms]
.
*** innerHTML ***
result : 829.987429[ms]
.
finish!

# Safari 3
preparing ...
let's go!
.
*** pure dom ***
result : 1005.991463[ms]
.
*** innerHTML ***
result : 200.991463[ms]
.
finish

# IE 6
preparing ...
let's go!
.
*** pure dom ***
result : 1921.985521[ms]
.
*** innerHTML ***
result : 1342.985521[ms]
.
finish!

# IE 7
preparing ...
let's go!
.
*** pure dom ***
result : 1890.984139[ms]
.
*** innerHTML ***
result : 1312.984139[ms]
.
finish!

# Opera 9.24
preparing ...
let's go!
.
*** pure dom ***
result : 2353.990287[ms]
.
*** innerHTML ***
result : 474.990287[ms]
.
finish!