.reduce

之前有人給我這様的一道題，設 A, B 為 string，編寫一個程序使得，當 B 的字母都在 A 出現過時，傳出 true，否則 false。例如 A = "abcde", B = "abc", 因為 B 中的 a, b, c 都在 A 出現過，因此我們的 funtion 要傳出 true。

因為沒有 .every 或 .reduce 等等的概念，第一次做的時候寫了兩個 for loop。然後答案使用 .every，嗯，知道多一個 method 也是好的。

最近在學習 .reduce，只要是需要對整個 array 的 entry 作 "consecutive action" (一個一個順序作一些 action)，都可以用 reduce 來解決。例如剛剛講到的 function 除了用 .every 外，還可以這様寫:

const containment = (string1, string2) => {
  const string1Array = string1.toLowerCase().split("");
  const string2Array = string2.toLowerCase().split("");

  return string2Array.reduce((A, char) => {
    return A && string1Array.indexOf(char) > -1;
  }, true);
};

好像有點太複雜 w? 我們來看看更簡單的例子，我們編寫 function maximum 來取得一個 number array 最大的數值:

const maximum = (...numbers) => {
  return numbers.reduce((A, b) => {
    return A > b ? A : b;
  });
};

這様一來 maximum(2, 3, 11, -2) 會 return 11。還是看不懂？我們現在就來講講 reduce 的概念﹗為了講得更仔細，無可避免要用數學一點的精確語言來解析。

假設我們有一個 array [a_0, a_1, ..., a_n]，給定一個 value A (不一定是 number)，從定義我們有

[a_0, a_1, ..., a_n].reduce(reducer, A) = 
reducer( ...reducer(reducer(reducer(A, a_0), a_1), a_2) , ..., a_n)

這實在太混亂了，為了簡化上式，我們來定義一個符號 $*$，我稱之為 action $*$，他是一個 binary operator 並且有 \[ A * b = \text{reducer}(A,b), \] (念作 A acts on b) 再加上我們濫用一下符號寫上 $* = \mathrm{reducer}$，由此以上的 "reducer" 公式其實單純是 \[ \begin{align*} &\color{white}{=} \text{[a_0, a_1, ..., a_n].reduce(reducer, $A$) } \\ &:=\text{[a_0, a_1, ..., a_n].reduce($*$, $A$) }\\ &=A * \text{a_0}*\text{a_1}* \cdots * \text{a_n} \end{align*} \] 這就是我所謂的 consecutive action，一個接着一個地進行。例如我們要找出 "maximum" 這個 function 怎様定義，很簡單，每一個 action 你都給我兩個數值之間的最大值就可以了﹗也就是說，定義\[ *:(A, b) \mapsto A*b:= \max(\{A,b\}) \] 因此編程上我們的 reducer 就寫成

reducer = (A, b) => {return A > b ? A : b}

至於上面的 containment，因為一理通馬國明，我就不作解釋了。

最後為甚麼 reducer 的第一個 variable 我們用 A，其實我們稱它為 Accumulator，他是一個 "累績" 目前所有階段的資訊的變量，最終它會累績所有階段的資訊，得出我們想要的答案。

我不明白 reducer 前覺得用傳統的 for loop 不是更簡單明確嗎？其實像上面 containment function 例子可以看到，for loop 寫得愈多，技術細節就會愈多，寫的人當下會寫得很開心。但如果你的 code 是要讓其他人看的，甚至是讓未來的自己看，要從那些技術細節猜想你的目的顯然不是容易的事。所以當大家都懂 reducer 的話，code 不但止可以寫得愈來愈短，code 本身也帶有一定的描述性了。

凡事總有兩面，需然只要是 for loop 都可以嘗試用 reducer 來代替，我就試着把一道以前用兩個 for loop 來做的題目變成 reduce 來解決:

https://leetcode.com/problems/longest-substring-without-repeating-characters/submissions/

然後我的解答:

var lengthOfLongestSubstring = function(s) {
    if (s.length < 2) return s.length;
    else {
        const stringArr = s.split("");
        const length = stringArr.length;

        let result = stringArr.reduce((A, char, index) => {
            let subString = stringArr
                .slice(index + 1, length)
                .reduce((A2, charOnRHS, index_2, arrToReduce) => {
                    if (A2.indexOf(charOnRHS) == -1) {
                        return A2 + charOnRHS;
                    } else {
                        //force the loop to break by mutating arr.
                        arrToReduce.splice(-(arrToReduce.length - index_2) + 1);
                        return A2;
                    }
                }, char);

            const subStrLength = subString.length;

            if (A.lenght == 0) {
                return subStrLength;
            } else {
                return A > subStrLength ? A : subStrLength;
            }
        }, 0);
        return result;
    }
};

我相信是我 reducer 用法不太妥當 ...，晚點再來改良。