Gauche:append-reverse

Gauche:append-reverse

Shiro(2011/04/29 13:39:57 PDT): ちょっと思ったので書き留めとく。

末尾再帰で値をconsしていって最後にreverse、というのは良く出てくるパターンだけど、 既に持っている結果の前に付け加えるものを計算するときにもそのパターンを使いたい、 ってことが時々ある。

最もナイーブなのは

 (append (reverse 累積した結果) 既に持っている結果)

とすることだけど、これはreverseで作ったリストをすぐにまたコピーしてるのと、 reverseで一回リストをなめて、またappendでなめるのが無駄でいやだ。 appendをappend!にすればコピーは減らせるけどなんか姑息。

そう感じるのは私だけではないようで、srfi-1にはappend-reverseという、 機能としては (.$ append reverse) と同じ動作の関数がある。

 (append-reverse 累積した結果 既に持っている結果)

ただしこちらはリストを一度しか辿らないし、余分なコピーもしないように 最適化されている。

だけどどうもこのappend-reverse、使ってみても収まりが悪い感じがしていた。 名前が強烈にappendとreverseの合成であることを示唆しすぎてて、 計算に無駄が無いことが直感的でないからかなー、とも思ってた。

最近もうひとつ、落ち着かない理由がわかった。 そもそもここでやりたいことを「appendとreverseの合成」ととらえるのが違うんじゃないか。

  (reverse xs)             ≡ (fold cons '() xs)
  (append-reverse xs tail) ≡ (fold cons tail xs)

なので、両者は本来同じ操作で初期値だけが違うと考えられる。いやむしろ、 後者の操作の方がよりプリミティブで、(reverse xs)はたまたま初期値が()である特殊例、 と考えた方が自然なんじゃないか。

それなのに後者をappendとreverseを使って理解するとまるでreverseの上位に来るようで、 この逆転が違和感の原因じゃないかなあと。

むしろreverseが2引数を取るようにして、1引数版はその特殊ケースと考えたらどうだろう。

  (reverse xs tail)
  (reverse xs) ≡ (reverse xs '())

reverseを「リストを反転する操作」と考えると違和感あるかもしれないけれど、 リスト構築子の一種と考えるとそうでもないんじゃないかな。 考えるほどにこっちの方が自然な気がしてくるんだけど。 2引数のreverseを持ってるLisp/Schemeって無いんかなあ。

More ...