リスト操作の罪悪感

Scheme をやっていて感じる罪悪感は、リスト操作の愚直性だ。

例えば、リストの長さを得る手続き list-length は

(define list-length
  (lambda (a)
    (let loop ((x a) (len 0))
      (if (null? x)
        len
        (loop (cdr x) (+ len 1))))))

こんな感じなんだけど、これを Java に直すと

int list_length(Object[] a) {
    Object[] x = a;
    int len = 0;
    while (true) {
        if (Arrays.equals(x, new Object[] {} )) {
            return len;
        }
        x++; // 先頭要素をなくした配列に変更するコードの代わり
        len++;
    }
}

という感じになる。

ただし、Java なら

a.length;

だけで配列のサイズは取得できるんだけど（リストならもちろん List#size() メソッドを使う）、Scheme だと愚直にリストを最後までたどらなければサイズを求められない。

つまり list-length の計算量はリストの長さに比例して O(n) だけのコストがかかる。それともライブラリ手続きである length は、Java の配列のように O(1) のコストでサイズを求められるのだろうか。

または、C 言語の strlen 関数なんかは、やはり対象の文字列の長さに比例したコストがかかるんだけど、普段そんなことを意識して strlen を使ってはいないはずで、それは strlen に渡す文字列がどれだけ長かろうが、十分高速に動作することを知っているからであって、Scheme の length も同様に意識するほどのことではないのだろうか。

リスト操作で reverse 手続きをよく使うことになるんだけど、これもドキドキしてしまう。例えば、リストの最後を切り離したい場合

(define sippo-kiri
  (lambda (a)
    (reverse (cdr (reverse a)))))

という具合に、2 回ひっくり返すことになる。やりたいことは単純なのに、やっていることと計算量が大げさな気がする。