文字列ポートを使おう - 主題のない日記

プログラミング言語 Scheme において少し気になる string-append の使い方の事例を見た。

これは、私が以前に append が気になるとして記事にした事例とよく似ている。図を描くのが面倒なのであらためて解説はしないが、空間的にも速度的にも本来なら O(n) のオーダーで出来るはずの処理を O(n²) にしているという意味で同じである。要するに無駄な中間状態を作っているのだ。 (注意：処理系が文字列の実装に rope などを使っている場合はそんなに差は生じない。ここでは素朴な処理系を前提としているが、一見して非効率なコードに見えても処理系によっては効率的な場合もある。)

R5RS の範囲内で平均的に性能が良い方法はおそらく結合すべき文字列をリストにまとめてから一気に string-append で結合する方法だと思う。 (末尾再帰にするともっといいかもしれない。)

(define (string-join-with-infix-and-newline string-list delim)
  (apply string-append
         (if (null? string-list)
             '()
             (letrec ((a (lambda(x) (if (null? x) '("\n") (cons delim (b x)))))
                      (b (lambda(x) (cons (car x) (a (cdr x))))))
               (cons (car string-list) (a (cdr string-list)))))))

さて、ここからが本題の文字列ポートの紹介である。もし処理系が文字列ポートをサポートしているならそれが使える。文字列ポートは SRFI-6 (Basic String Ports) として提案され、 Script-Fu を含む多くの処理系で採用されている。 R6RS や R7RS では仕様自体に取り込まれた。 (R6RS の文字列ポートは SRFI-6 とは使い方が異なることに気をつけること。)

上述のコードを文字列ポートを使って書き換えるとこのようになる。

(define (string-join-with-infix-and-newline string-list delim)
  (if (null? string-list)
      ""
      (let ((port (open-output-string)))
        (display (car string-list) port)
        (for-each (lambda(x) (display delim port) (display x port))
                  (cdr string-list))
        (newline port)
        (get-output-string port))))

あたかもファイルに出力するのと同じような書き方で文字列ポートに蓄積して、最後に文字列として取り出すという操作で文字列を構築する。 I/O と共通の操作で文字列構築ができるというのはとても使い勝手がよいし、一般的には性能もよい。 Scheme で文字列の処理をするには文字列ポートはなくてはならないものだと私は感じている。

Document ID: 11a193e8d0f408bb591f09f17be3c315