継続のすばらしさ

Haskellでやると書いておいて、Pythonでやっちゃう罠。
Pythonがサポートしている中途半端な継続ことgeneratorでsortすれば、遅延評価と同じく、「先頭n個だけ使う」という用途では後半のsortを実行しないで済む。

>>> l = [3,5,2,1,4,5,8,2]
>>> def lazy_sort(lst):
	if len(lst) == 0:
		return
	mid = lst[0]
	left = []
	right= []
	for v in lst[1:]:
		if v < mid: left.append(v)
		else: right.append(v)
	lg = lazy_sort(left)
	for y in lg: yield y
	yield mid
	rg = lazy_sort(right)
	for y in rg: yield y
	
>>> s = lazy_sort(l)
>>> s.next()
1
>>> s.next()
2
>>> s = lazy_sort(l)
>>> list(s)
[1, 2, 2, 3, 4, 5, 5, 8]

読んだら判ると思うけど、再帰しようとしたら自分がgeneratorだったから、再帰するたびに一旦generatorを作っている。Pythonのインタプリタがどう実行するのかイマイチ理解していないが、よっぽど凄い最適化をしてくれない限りは非常に効率が悪そう。
最初から再帰をしないで書くのが正攻法だろうけど、クイックソートって再帰で書きたくなるよね。

このブログに乗せているコードは引用を除き CC0 1.0 で提供します。