Schemeの(fold-left append '() all-freqs)の意味が分からない

Question

Schemeで書かれた状態密度を求めるコードを解読しています。

この中で次のようなfold-leftという関数が登場しており、何をしているのかが分かりません。

(define (all-freqs-broaden)
  (broaden (fold-left append '() all-freqs)))

all-freqは2次元配列で
all-freq[i] が i番目のk点の共鳴周波数の配列
だと理解しています。

上のコードが何をしているのか分かる方いらっしゃったらご教示お願いします。

Answer 1

fold 系関数は畳み込みと呼ばれるパターンを処理するもので、そのバリエーションについては以下の URL にある図がわかりやすいです。

http://blog.practical-scheme.net/shiro/20120314-fold

では具体的に (fold-left append '() all-freqs) が何をやっているのかというと、リストに含まれる複数のリストをつなげようとしています。

例えば all-freqs の中身が '((a b c) (d e f) (g h i)) であったとしたら、この処理を通した結果は '(a b c d e f g h i) というように、括弧を一段階はがしたような形になります。

Comments

[ruei]

なるほど、リンク先のopというのはopという演算によってつなげるということを表しているんですね。

この場合だと、各k点について周波数のリストがあったのを一個のリストにまとめているんですね。

'((a b c) (d e f) (g h i)) が '(a b c d e f g h i) になるという例がめっちゃわかりやすかったです。

ありがとうございます。

[SaitoAtsushi]

質問の範疇から外れるので余談ではありますが、 fold-left に append を渡すのはあまり効率の良くないコードである可能性があります。 append は引数の最後に渡されたリストは結果と共有する、逆に言えば最後の引数以外はコピーが生じます。 fold-left の順序で append を適用すると最終的に捨てる無駄なコピーをたくさんやってしまいます。
似たような事例について説明を書いたことがあるので参考にしてください。
https://saito.hatenablog.jp/entry/2014/03/28/184636

fold-left のかわりに fold-right を使えばコピーは一度だけになるので無駄が少なくて良いでしょう。 fold-left よりも fold-right の方がスタックを消費する可能性がありますが、無駄なコピーをするよりはたぶんマシです。

あるいは、もし使っている処理系が srfi-1 をサポートしているのであれば concatenate が使えるかもしれません。 concatenate はリスト中のリストを結合する手続きです。 ただし、結果として出力されるリストの一部が元リストと共有されるので、それが問題にならないかどうか用途に対して注意深く検討する必要があるかもしれません。