読者です 読者をやめる 読者になる 読者になる

Schemerは再帰を使わない

プログラミング言語schemeLispの一種である。Lisp系全般に共通するようにschemeもまたリストを基本的なデータ構造として活用する。そして、反復処理には再帰を基本的な考え方とする。はてなダイアリキーワードにおいてもSchemeの項には「Schemeプログラマはループよりも再帰を好む」と書かれている。
ところで、SICPの問題を解いた過程を記事にしている人が少なからずいるが、それを見ていて気付くことがある。例えば以下のような関数を見てみよう。

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      '()
      (cons (accumulate op init (map car seqs))
            (accumulate-n op init (map cdr seqs)))))
http://d.hatena.ne.jp/comeinto/20080510#1210434497

schemeに慣れた人であればこれはどこかで見たことがあるだろう。そう、srfi-1で定義されているunfold関数のパターンだ。
unfoldを使って定義しなおしてみる。

(define (accumulate-n op init seqs)
  (unfold (compose null? car)
          (lambda(x) (accumulate op init (map car x)))
          (cut map cdr <>)
          seqs))

残念ながらこの場合では短く表現できるわけでもないし、わかりやすくなるわけでもない。だが、unfoldというひとつのパターンとして表現できるということが重要だ。unfoldに限らずSICPの問題に登場するようなパターンのいくつかは基本的な関数として用意されている。先人達はこれらがありきたりなパターンであることを看破していたのだ。
で、何が言いたいのかと言うと、schemeでは再帰的な考え方を多用するのは確かだとしてもありきたりなパターンは抽象化された関数を使うので、世間で言われるほど再帰ばっかりしてるわけではないと言うこと。
Document ID: db168d9c5351123dde662e0833082b85