2012-10-07-01-アルゴリズムとクロージャと
>> Site top >> weblog >> 月別アーカイブ >> 2012年10月のlog >> 2012-10-07-01-アルゴリズムとクロージャと
最終更新日付：2012/10/07 01:00:00
アルゴリズムとクロージャと
2012 年 10 月 07 日
以前書いたとおり、最近は Common Lisp で STL アルゴリズムと同じようなものを作っている。最初に書いたのは、ひとまず以下のようなものだった。
(defun copy-if (seq pred)
(labels ((list-imp (lst acc)
(if (null lst)
(nreverse acc)
(let ((itm (car lst)))
(if (funcall pred itm)
(push itm acc))
(list-imp (cdr lst) acc))))
(array-imp (idx cnt acc)
(if (<= cnt idx)
acc
(let ((itm (aref seq idx)))
(if (funcall pred itm)
(vector-push itm acc))
(array-imp (1+ idx) cnt acc)))))
(cond ((listp seq)
(list-imp seq nil))
((arrayp seq)
(let ((cnt (length seq)))
(array-imp 0 cnt (make-array cnt :fill-pointer 0))))
(t (error "not a sequence.")))))
きっと、Lisp に慣れた人が見たら「変なコード」なのだろう。まだ手習いの段階なのでどうか勘弁して欲しい。今は「どこがどう変なのか」に気付こうとしている段階なのだ。
それはそれとして、これは copy_if だ。シーケンスを受け取り、条件を満たす要素だけを返す。STL ならば入力反復子の組みを受け取り、出力反復子に結果を書き出す。しかし、上記のコードはそもそも反復子の概念を使わず、シーケンスとしてリストか配列だけを受け付ける。シーケンスの一部分を渡すこともできないし、入力の種類（リストか配列か）に従って出力に同じ種類のシーケンスを新規に作成して返している。入力シーケンスが配列の場合、出力用に同一要素数の配列を作成してからローカルの末尾再帰関数に渡している。極端な ── 何万という入力に対して数個の出力が予想されるような ── 状況では、とても実用に耐えるものではない。
まぁ手習いだし、と思いながらこんな感じで40個くらいのアルゴリズムを（簡単なものから）書いていったのだが、あるときふと気付いた。クロージャで反復子を表現できるんじゃないのかな‥‥‥と。
大した話ではないけれど、続きは次回。
コメント
このページのタグ
Page tag : Common Lisp
Copyright(C) 2005-2021 project-enigma.
Generated by CL-PREFAB.
