2012-10-07-01-アルゴリズムとクロージャと

>> Site top >> weblog >> 月別アーカイブ >> 2012年10月のlog >> 2012-10-07-01-アルゴリズムとクロージャと

最終更新日付：2014/01/02 00: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-2017 project-enigma.
Generated by CL-PREFAB.