FoldLeft

FoldLeftという考え方について。
（関数型プログラミングについて初学者が錯綜しているので話半分で）

例によって1から9までの数字を足した結果を求めよ、というプログラムの話になるんだけど
とあるScala講義(どこかの大学かな)でこんな話をしていた。

■この教室にいる人全員の年齢を足した結果を求めたい

一つのやり方は、まず1枚の紙を用意して端の人に渡す。その人は年齢を書いて次の人に渡す。
次の人は紙の数字を、自分の年齢を足した数に書き直して、また次の人に渡す。（鉛筆と消しゴムを使うんだろう）。
これを終わりの人まで繰り返す。最後の人は紙を教師に渡して完成。
このやり方は、totalという変数を用意し、forループ内でどんどん数を足していく従来のプログラミングとおんなじだ。

もう一つのやり方は、（全員が紙を持ってるとして）最初の人は自分の年齢を書いた紙を次の人に渡す。
次の人はその数と自分の年齢を足した数を別の紙に書いて次の人に渡す。 これを終わりまで繰り返す。
これで完成で良いんだけど、より正確には最後の人は自分の年齢を足した数を書いた紙を前の人に戻す。今度はどんどん前の人に戻して最初の人まで戻ったら教師に渡すというやり方にする（ちょうど最後の人は教室の後ろの席だとすればなんとなくわかる）。
どんどん新しい紙にするという部分が最初のやり方と違う。
プログラミングで考えると、totalという変数に当たるものが無い。
最初の人から最後の人まで繰り返すという言葉に反して、このやり方をループで書くのはしんどい（紙を変数に見立てた場合）。

これを再現するのが関数型の書き方で再帰を使った書き方になる。以下はJavaScriptでの実装例（だと思う）。

var list = [1,2,3,4,5,6,7,8,9]

var f = function(val, list){
  if (list.length === 0) {
    return val
  } else { 
    var e = val + list.shift()
    return f(e, list) 
  }
}
console.log(f(0, list)) 

うーん、ちょっと何やってるか分かんないと思う。どうせうまく説明できないが説明すると、fという関数は初期値0と数値のリストを渡される。
1. リストが空なら第一引数のvalをそのまま返す。
2. リスト内に数値があれば先頭の数を足し、その数と残りのリストでもう一度fを呼び出す。
3. 残りのリスト内にまだ数値があれば先頭の数を足して、その数と残りのリストでまたfを呼び出す。
...
x. 最後まで行くと全部足した数と空のリストでfが呼び出されるので、全部足した数が返される。
再帰なので最後まで行くと一気に最初の関数呼び出しのとこまで戻されることになる。

list.shift() というのが微妙なとこだ。
リストの先頭の要素を取り出す関数だが、取り出すと本当にリストから削除される、popのような関数だ（popは後入れ先出しなのでそこが異なる、どっちかというとQueueかな？）。
var e = val + list.shift() だけで先頭要素と足し合わせるのと、先頭を除いた残りのリスト、というのをやっている。
これなら順次新しい紙を用意して足し算し、次の人（残りの人）に渡すというようなやり方に沿ったプログラムになってると思う。

この順々にやる方法がFoldLeftという考え方だ（もしかしてFoldRightかも）。
リスト先頭の要素と、何の処理をするか（今回は足し算）と、リストの残りは再帰でやる、という戦略。

せっかくなので全部書こうと思う。
何の処理をするか、というfunctionをfに渡すように作ると汎用的になる。また、リストの先頭要素と残りのリストをそれぞれ分かりやすくlist_headとlist_tailとした。

var list = [1,2,3,4,5,6,7,8,9]

var f = function(val, list, f2) {
  if (list.length === 0) {
    return val
  } else { 
    var list_head = list[0]
    var list_tail = list.slice(1)
    var e = f2(val, list_head)
    return f(e, list_tail, f2) 
  }
}

var plus = function(a,b) {
  return a+b
}

console.log(f(0, list, plus))

となる。リスト内の要素を全部掛け合わせた結果が欲しいなら、

var product = function(a,b) {
  return a*b
}

console.log(f(1, list, product))

となる（最初の値は1に変わる）。
この辺まで考えると、リスト内の数値を全部足した結果を返す、全部掛けた結果を返す、という専用の関数を作りたくなるはず。

var f = function(val, list, f2) {
  if (list.length === 0) {
    return val
  } else { 
    var list_head = list[0]
    var list_tail = list.slice(1)
    var e = f2(val, list_head)
    return f(e, list_tail, f2) 
  }
}

var plus_all = function(list) {
  var plus = function(a,b) {
    return a+b
  }
  return f(0, list, plus)
}

var product_all = function(list) {
  var product = function(a,b) {
    return a*b
  }
  return f(1, list, product)
}

var list = [1,2,3,4,5,6,7,8,9]
console.log(plus_all(list))
console.log(product_all(list))

FireBug等で動くのが分かるだろう。関数型プログラミングになってるはずだ。どんなもんだろう。
plus とか product が関数の中で定義されてるのがちょっとこざかしい感じがする。

---

関係ないが今年度の新人研修に関わることになって、プログラム言語研修に何の言語を使うかが議論となった。今まではC言語だったのが、Cは古い、もっとプログラミングそのものを教えるのに適した言語があるんじゃないか、という話になり、JavaScriptで研修を行うことになった。
その方針だけ決めて講師は社内のエンジニアを適当にアサインしたのだが、どうも比較演算子には「==」と「===」があるとか、「1 === "1"」はFalseだが「1 == "1"」はTrueになるという内容を教えたらしい。また、JavaScriptには型が無く、数値の足し算のつもりが文字列の連結になるぞ、というようなことを教えたらしい…。
JavaScirptを選択した主旨が伝わってないじゃん。そんな言語仕様ばっかり教えるならCを教えた方がまだ良かったんではないかと。
JavaScriptを教えたいんじゃなく、プログラミングを教えたいだけだったんだけどな。

純粋にプログラムを教えるために余計な言語仕様にとらわれない言語としてJavaScriptって個人的には悪くないと思った。BestとかExcellentではないけどCやJavaと比べれば、Not badと思ったんだけどな。でも初心者を打ちのめすのに効果絶大な言語仕様も多いから、講師のセンスだな。
手続き型としてはコールバックが多用されるのが難しいというのはあると思う。