iT邦幫忙

2018 iT 邦幫忙鐵人賽
DAY 7
2

本章重點

  • Reduce 用以合併 Array ,因為不強制回傳 Array ,使它的彈性更大。
  • FP 大多是 表達式 (Expression) ,而非 陳述式 (Statement)
  • 每個 Express 意圖清楚,可以輕易被組合、修改、獨立被測試。

在開始之前

這兩篇有大量的 JS 語法講解,如果你覺得看不太懂程式碼,可以先看看這兩篇。
關於 Map 與 Filter ,收入在第二篇,也建議各位可以先看看。

Reduce

Reduce 又稱為 Fold,顧名思義會迭代 Array ,並且把它折疊(或者是說合併)。

Reduce 就與 Map 跟 Filter 不同了,
Redcue 須傳入 function 與 初始值 ,且 Reduce 是依序接到四個變數︰

  • accumulator
    • 累積值,在第一輪時會是 初始值
      接下來會是 function 回傳的結果。
  • element (value)
    • 當前的元素。
  • index
    • 當前的 index。
  • array
    • 目前正在迭代的 array。

由同樣的程式瑪觀察。

[1,2,3,4,5].reduce(console.log)

// // output
// 1 2 1 (5) [1, 2, 3, 4, 5]
// undefined 3 2 (5) [1, 2, 3, 4, 5]
// undefined 4 3 (5) [1, 2, 3, 4, 5]
// undefined 5 4 (5) [1, 2, 3, 4, 5]
// undefined

因為並沒有初始化 accumulator,所以會從第一項開始做,之後因為 console.log 沒有回傳值,所以 accumulator 成了 undefined 。

以下例子是總和一個 Array 。

const array = [1, 2, 3, 4, 5]
Object.freeze(array)

console.log(
    array.reduce((acc, el) => acc + el, 0) // 15
)

Reduce 的遞迴實作︰

const reduce = func =>
    acc => 
        array => {
	        if (array.length == 0) {
		        return acc
            } else {
                // 取出 head 與 tail
		        const [x, ...xs] = array
		        // 計算 acc 後, tail 繼續遞迴 reduce
                return reduce(func)(func(acc, x))(xs)
	        }
        }

因為 Reduce 不強制要傳回 Array ,而且沒有其餘限制,使它可以作到更多事情比別人,像是 maxmin ,也可以回傳 array ,像是 reverse

// 不回傳 Array
const max = reduce((acc, el) => (acc > el ? acc : el))(-Infinity)
const min = reduce((acc, el) => (acc < el ? acc : el))(Infinity)

// 回傳 Array
const reverse = reduce((acc, el) => [el, ...acc])([])

在 JS 中, Array.reverse 並不是 pure function

它會嚼爛你的 Array,很恐怖,我們修正它。

Array.prototype.reverse = function() {
	return this.reduce((acc, el) => [el, ...acc], [])
}

來點實際的例子吧

那來看看我最近面試實習的考題吧。(在網路上也查的到面試考題,應該沒關係。)

  1. 印出 倒三角
*****
****
***
**
*
  1. 印出 等腰三角形
    *
   ***
  *****
 *******
*********

真的,是真的考印星星喔。

倒三角

先以我們熟悉方法寫看看。

const answer1 = length => {
	let stars = ''
	for (let i = length; i > 0; i--) {
		for (let j = 0; j < i; j++) {
			stars += '*'
		}
		stars += '\n'
	}
	return stars
}

console.log(answer1(3))
// output
// ***
// **
// *

沒什麼難度,那我們把它變得 functional 一點。
首先我們需要兩個產生 Array 常用的 functionrangerepeat

const range = length => Array.from({ length }, (_, i) => i)
const repeat = length =>
    x => Array.from({ length }, _ => x)

先別關掉分頁,我可以解釋, Array.from 一共接三個參數︰

  • 類 Array
    一個具有 1, 2.. 或是有 length 的 Object。
    所以這邊會產生 長度為 length 的 [undefined, undefined..]
  • Map Function
    就是一個普通的 Map。
    在 range 會回傳 index , repeat 則是重複某個值。
  • this
    會傳入 Map 的 this ,沒用上。

好,那來變出一點星星吧!

const answer1 = length =>
	range(length)
		.reverse()
		.map(length => length + 1)
		.map(length => repeat(length)('*').join(''))
		.join('\n')

console.log(answer1(3))
// output
// ***
// **
// *

好多了,但讓我試著增加一點可讀性。

const makeStars = length => repeat(length)('*').join('')
const increment = x => x + 1

const answer1= length=>
       range(length) // [0, 1, 2]
    		.reverse() // [2, 1, 0]
            .map(increment) // [3 ,2 ,1]
            .map(makeStars)//['***' ,'**', '*']
            .join('\n')

console.log(answer1(3))
// output
// ***
// **
// *

這個版本是不是很容易看懂的多呀,每個動作都很清楚、彈性較大,可以拉上去比較看看,看看自己喜歡哪一種。
如果不想印成倒的呢?拿掉 reverse 就行了!

等腰三角形

剛剛那題實在輕輕鬆鬆,讓我們試試第二題。

這題比較複雜,先來看看小型的吧,如果你對程式碼相當有自信也可以直接看 code 。

  *  
 *** 
*****

星星的分佈大概如下︰

層數 空白 星星
0 0, 1, 3, 4 2
1 0, 4 1, 2, 3
2 0, 1, 2, 3, 4

觀察得知︰

  • 每層共有 塔長 * 2 - 1 的字元量
  • 當字元在 塔長 - 1 位置必為星星
    每多一層在 塔長 - 1 ± 層數 的地方也為星星
const answer2 = length => {
	let stars = ''
	for (let i = 0; i < length; i++) {
		for (let j = 0; j < length * 2 - 1; j++) {
			if (j <= length - 1 + i  && j >= length - 1 - i) {
				stars += '*'
			} else {
				stars += ' '
			}
		}
		stars += '\n'
	}
	return stars
}

console.log(answer2(3))
// output
//   *  
//  *** 
// *****

有點複雜,是時候來 functional 一下了。
當看到 *** ,我有想我需要一個 Funciton 在 兩端加上 * 或空白

const wrapSomething = wrapper => 
    center => wrapper + center + wrapper

const wrapStars = wrapSomething('*')
const wrapBlanks = wrapSomething(' ')

console.log(
    wrapStars('*'), // ***
    wrapBlanks('***'),//  ***  
)

如此只要重複呼叫這兩個 Function 就好了,因此我們需要 applyTwice 的強化版, applyMany

const applyMany = func =>
    x => 
        times => {
	        if (times == 0) {
		        return x
        	} else {
		        return applyMany(func)(func(x))(times - 1)
	    }
    }

const wrapManyStars = times => applyMany(wrapStars)('*')(times)
const wrapManyBlanks = times =>
    stars => applyMany(wrapBlanks)(stars)(times)

console.log(
    wrapManyStars(0), // *
    wrapManyStars(1), // ***
    wrapManyBlanks(1)('***') //  *** 
)

那我們需要 wrap 幾次呢?

層數 空白次數 星星次數
0 2 0
1 1 1
2 0 2

還記得昨天的 zip 嗎?

const zip = array1 => array2 => {
	if (array1.length == 0 || array2.length == 0) {
		return []
	} else {
		const [x, ...xs] = array1
		const [y, ...ys] = array2
		return [[x, y], ...zip(xs)(ys)]
	}
}

const answer2 = length => {
	const starLengths = range(length)
	const blankLengths = range(length).reverse()

	return zip(starLengths)(blankLengths)
		.map(([sl, bl]) => {
			const stars = wrapManyStars(sl)
			return wrapManyBlanks(bl)(stars)
		})
		.join('\n')
}

console.log(answer2(3))
// output
//   *  
//  *** 
// *****

完成!

總結

在 FP 中有一些函數需要被額外實作,像是 rangerepeatzip ,這些函數應該被寫成 Module ,我推薦使用 Ramda.js,用法與今日的 code 幾乎一模一樣。
如果是使用純 FP 語言,像是 Haskell ,語法會更加精簡,你可以在 這裡 參考 Haskell 的版本。

撇除掉這個部份,很容易發現:

  • FP 大多是 表達式 (Expression) ,而不是 陳述式 (Statement)
  • 每個 Express 意圖清楚,可以輕易被組合、修改。
  • 每個 Express 都可以獨立被測試。

另外複習一下︰

  • 每個 Expression 必須是 Pure Function ,保證沒有副作用。
  • 為了把 Expression 寫的漂亮,遞迴對 FP 很重要。
  • Higher order Function 以 Function 產生 Function ,有很高的彈性。

後記

這家是感謝信 QQ。

今天的內容真的很長,非常感謝看完整篇文章的你,如果有任何心得、想法、問題,都歡迎留言給我。
明天我們正式來面對 Curry 吧!

題外話,第二題有另一個觀點:無視右邊的空白

層數 空白數量 星星數量
0 2 1
1 1 3
2 0 5
const answer2 = length => {
	let stars = ''
	for (let i = 0; i < length; i++) {
		for (let j = 0; j < length - i - 1; j++) {
			stars += ' '
		}
		for (let j = 0; j < i * 2 + 1; j++) {
			stars += '*'
		}
		stars += '\n'
	}
	return stars
}

console.log(answer2(5))

不過面試時來不及想,這個版本也簡潔很多。

參考資料


上一篇
Higher order Function = { Map, Filter } 與 Recursion
下一篇
Higher order Function = { Curry } 與 Type Signature
系列文
30天快樂學習 Functional Programming14

尚未有邦友留言

立即登入留言