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.