foldを学ぶ

scheme

今日もschemeやってます。継続的に打ち込めると吸収度が違いますね。

foldとは

リストの要素を順に走査しながら手続きを行える事ができるのが、foldという手続きらしい。

具体的にどういった事ができるのかといいますと、２つの引数を元にリストのcdrポインタが空リストになるまで手続きを続けるということでしょうか。

パラメータ

  • 第1引数
    • 初期値
  • 第2引数
    • リスト

挙動を順に分解するとこんな感じ。

(fold + 0 '(1 2 3))
  1. (+ 0 1)
  2. (+ ↑の結果 + 2)
  3. (+ ↑の結果 + 3)
  4. ;result => 6

フムヌク本の47Pにわかりやすい例が書いてありました。

init = <初期値>;
lis  = <リスト値>;
while(listが空でない事){
	init = <手続き> (car(lis), init);
	lis  = cdr(lis);
}

foldの考察

car部ポインタを取得して手続き評価し第1引数へ、cdr部ポインタを第2引数に渡し空になるまで再帰的に評価し、最終的に評価されたS式を返す。これがfoldの実装っていう事で良いのかな？

使い方は理解できました。理論があっているかは少しだけ自信あり。

一言で言い表す説明を書籍から発見！

「foldは次の式の値を求める」と説明できる。

なるほどわかりやすい。

foldを利用する

この例題の手続きにしましょうというのがあるので、真似してやってみる。

sum.scm

(define (sum-of-numbers lis)
    (fold + 0 lis))
(print (sum-of-numbers '(1 2 3)))
(print (sum-of-numbers '(5 6 7)))
(print (sum-of-numbers '(0 1 2)))

listのsum関数ですね。
これをコマンドラインから実行すれば

$gosh ./sum.scm
6
180
3

と表示されました。やった！

foldの使い道とか利用方法がわかった。
まだまだ続きがあるようなので、今日は切りのよい所までにして、続きは明日以降に持ち越します。