JavaScript: 「最初はこうだったけど、いろいろあって、こうなった」reduceは状態遷移だ


と考えるとより幸せになれるのでは?、という記事です。
Array.prototype.reduce()をガンガン使おうの主旨に賛同したので書いてみました。

要約:

//初期状態:
const initModel = (/* 初期状態 */)
//状態 model と ひとつのメッセージ msg から 新しい状態 を返す:
const update = ( model, msg ) => ( /* 新しい状態 */)
//メッセージの配列 msgs で初期状態 initModel を次々とアップデートした結果:
const processed = msgs => msgs.reduce( update, initModel )
// msgs 以外の引数を追加したい時:
//追加の引数 x で初期化:
const initModel = x => (/* 初期状態 */)
//追加の引数 x と 状態 model と ひとつのメッセージ msg から 新しい状態 を返す:
const update = x => ( model, msg ) => ( /* 新しい状態 */)
//追加の引数 a, b と メッセージの配列 msgs で初期状態 initModel を次々とアップデートした結果:
const processed = a => b => msgs => 
  msgs.reduce( update(a), initModel(b) )

わかち書きしただけですが、こういう風に考えるだけで reduce がより理解しやすいし、複雑なこともreduceで書きやすくなる(のでは?)

reduce とは?

reduce() は配列の各要素に対して(引数で与えられた)reducer 関数を実行して、単一の値にします。
(引用:MDN:Array.prototype.reduce())

要するに、配列を関数を使ってひとつの値にすること、です。

ここで主役は「配列」と 「関数」。
「初期値」は省略可能で、配列が空の可能性がある場合やより複雑な計算をしたい場合に使用する、いわばゲスト扱いです(もちろん使ってもいいし、むしろ使うことが推奨されているんですけども)。

ここで、発想を逆転させてみます。

主役は 「初期値」 と 「関数」。

そして「配列」は「初期値」を変化させるためのもの。
配列の要素は、毎回登場するゲスト。

こう考えても、初期値が必須になること以外(そしてそれは望ましいこと)、計算上は違いはありません。

//初期値:
const init = (/* 初期値 */)
//累算器 acc と 配列の要素 e から 次の acc の値 を返す:
const reducer = ( acc, e ) => ( /* 新しい acc */)
//配列 array で初期値 init を次々と変化させた結果:
const result = array => array.reduce( reducer, init )

何がうれしい?

初期値があるので、空の配列でもエラーをださない

まあこれは当然。

過程が直観的にわかりやすい

見た目上で
init -> acc -> 新しい acc -> result
と、順番に出てくるので、
「配列を関数を使ってひとつの値にする」だったものが、
「最初はこうだったけど、いろいろあって、こうなった」という風に見えてきます。

初期値(そしてacc、result)と e がそもそも種類が違うものだと思える

「配列を関数を使ってひとつの値にする」と聞くと、なんとなく、初期値、acc、resultと 配列の要素 e が同じ種類のものだと思っちゃいませんか?
同じ種類では済まない計算をしなければいけなくなると、途端に複雑に思えてきます。

最初から違う種類だと思っていると、シンプルに考えられるので、より複雑な計算にも単純なものと同じ手法で取り組めます。

で? acc をどうする?

累算器 acc の初期値が init で 結果が result なので、acc をどんなものにするか? が重要です。
答え:計算に必要なもの全部を含める。
といっても次の3パターンで十分でしょう。

  1. 答になるものだけ (比較的簡単な計算の場合。それでいけるのならそれで)
  2. 答えになるものとそれを計算するのに必要なものたち
  3. 最終的な答を計算するのに必要なものたち

必要に応じて配列、オブジェクト、Map、Setなどを用いて、ひとつにまとめます。

累算器 acc から状態 model へ

配列の要素がひとつ来るごとにこの acc が変化していく、という意味で 累算器 acc を 状態 model と呼ぶことにします。
同様に状態を変化させる、という意味で reducer関数を update と呼ぶことにします。

//初期状態:
const initModel = (/* 初期状態 */)
//状態 model と ひとつのメッセージ msg から 新しい状態 を返す:
const update = ( model, msg ) => ( /* 新しい状態 */)
//メッセージの配列 msgs で初期状態 initModel を次々とアップデートした結果:
const processed = msgs => msgs.reduce( update, initModel )

配列は msgs,結果は processed にしてみました。
すべて呼び名を変えただけです。見た目以外は何も変っていません。
ですが、「最初はこうだったけど、いろいろあって、こうなった」感が増したと思いません?

また、実際に使ってみると、msgs以外の引数も欲しくなってきます。
そんな場合は こんな方法で initModel, update に引数を渡します。

// msgs 以外の引数を追加したい時:
//追加の引数 x で初期化:
const initModel = x => (/* 初期状態 */)
//追加の引数 x と 状態 model と ひとつのメッセージ msg から 新しい状態 を返す:
const update = x => ( model, msg ) => ( /* 新しい状態 */)
//追加の引数 a, b と メッセージの配列 msgs で初期状態 initModel を次々とアップデートした結果:
const processed = a => b => msgs => 
  msgs.reduce( update(a), initModel(b) )

能書きはここまでです。
実際使って書いてみます。

reduceの結果がそのまま答になるパターン

sum

const initModel = 0
const update = (model, d) => model + d
const sum = msgs => msgs.reduce(update, initModel)

const items = [0, 1, 2]
sum(items)  // -> 3

みんな大好き sum です。
「初期値 0 にメッセージを次々足していったら sumになる」これは簡単ですね。

Array.prototype.map風

元記事にならってもうひとつ。実用性はありません。

const initModel = []
const update = (model, d) => [...model, msg * 2]
const mul2 = msgs => msgs.reduce(update, initModel)

const items = [0, 1, 2]
mul2( items )// -> [0, 2, 4]
// ≒items.map(item => item * 2)

reduceの結果から答を取り出すパターン

ちょっと複雑になってきます。

PassingCars

Codilityより。
配列の要素 0 が東向きの車、1 が西向きの車を表していて、車同士がぜんぶで何回すれちがうか?というような問題のようです1。くわしくは先人の挑戦からどうぞ。

const initModel = {east: 0, passing: 0}
const update = ( model, msg ) => 
  msg === 0 ? {...model, east: model.east + 1}
  : {...model, passing: model.passing + model.east}
const processed = msgs => msgs.reduce(update, initModel)

const items = [0,1,0,1,1]
 processed( items ).passing  // 5

updateの中味が多くなったのと、最後の答の引き出し方がちょっと違うだけです。
状態としては、東向きの車の数 east、西向きの車の数 west、すれちがいの数 passing が考えられますが、実際やってみると west は計算にかかわらないので、 状態の形は:
{east:(整数), passing:(整数)}
となります。
updateでしていることは、

  • model と msg から、
  • 東向きの車が来たら east をひとつ増やし、
  • 西向きの車が来たら、passing を east だけ増やした、
  • 新しい model を作って返す、

ということです。
最終的にはreduceした結果からpassingだけを取り出しています。

最終的な答を計算するのに必要なものをreduceで求めるパターン

いい例が思いつかなかったので、再びパクりです。

TapeEquilibrium

同じくCodilityより。
整数の配列を、できるだけそれぞれの総和が同じに近付くように二つにわけたとき、ふたつの総和の差の絶対値は?というような問題のようです(かなり意訳しました)。くわしくは先人の挑戦より。

const initModel = [0]
const update = (model, d) => [...model, model[model.length - 1] + d]
const scanAdd = msgs => msgs.reduce(update, initModel) 
//総和と累積和から、そこで切った場合のそれぞれの配列の総和の差の絶対値を求める関数
const absDiff = total => partial => Math.abs(2 * partial - total)  

const items = [3,1,2,4,3]
const scanned = scanAdd(items)
const total = scanned[scanned.length - 1]
Math.min( ...scanned.map( absDiff(total) ) ) // 1

この問題は配列の総和と累積和(配列の先頭からその要素までの和)をとっておくと、比較的簡単に計算できそうな問題です。
reduceには、総和を計算するときに、ついでにこの累積和を計算してもらいます。
その後、ふたつにわけた配列それぞれの総和の差の絶対値を、すべての場所で計算して、最小値を取っています。

まとめ:

自分の求めているものとのずれで3パターンにわけてみましたが、reduceする部分だけ見れば実はどれも同じです。
日頃のプログラミングのなかで「最初はこうだったけど、いろいろあって、こうなった」パターンが現れたら、そこには reduce が使えるかもしれない、と思ってもらえたらさいわいです。


  1. 道路の西の端で観測する、とかの条件なのかな? 場所によって計算が変ってくると思う...