iT邦幫忙

2018 iT 邦幫忙鐵人賽
DAY 8
0

本章重點

  • Haskell 與 Curry ,命名於 Haskell Brook Curry,一位研究組合子邏輯的數學家。
  • Curry 接受足夠參數後即會執行,add(1, 2)add(1)(2) 皆會執行,在 JS 藉由 Function.bind 實作。
  • Type Signature 可以幫助 快速了解 Funtion 的目的和行為、大幅增加可讀性,在編譯時能做 Type Check,在 FP 扮演舉足輕重的地位。
  • 為了交換輸入順序,通常使用 Lamda 重新包裝函式 ,在 Ramda.js 中,有 __ (double underscore) Placeholder 的特殊用法。

在開始之前

這兩篇有大量的 JS 語法講解,如果你覺得看不太懂程式碼,可以先看看這兩篇。

Haskell Curry

Curry 一詞來自 Haskell Brook Curry ,是一位美國數學家與邏輯學家,專長於組合子邏輯理論,以 Curry paradoxCurry–Howard correspondence 聞名,在數理邏輯和計算機科學上是里程碑的存在, Haskell (在昨天提及的純 FP 語言)Curry 都是以他的名字來命名。

所以跟 NBA 沒關係喔!

你已經會 Curry 了!

Curry 的概念很簡單, 參數足夠就執行,不夠就會傳 Function ,在昨天的 應用實例 大量使用(如果你還沒讀過,我建議你可以先看看)。
另外在純 FP 語言中,所有 Function 皆是 Auto Curry 。

const add = x => 
    y => x + y

const add2 = add(2)

cosole.log(
	add2 // y => x + y
)

console.log(
	add2(3) // 5
)

add 接受 x 回傳 Funtcion y => x + y ,在 add2 當中,回傳 Function 形同 y => 2 + y ,它成了一個新的 Function ,這就是 Curry 。

但 add 與真正的 Curry 還有點距離,真正的 Curry 應該能被以 add(2, 3) 的模式被執行。

add(2) // y => 2 + y 
add(2)(3) // 5

// 不符合預期 QQ
add(2, 3) // 預期 5 , 但目前回傳 y => 2 + y

真正的 Curry

為了真正實作 Curry ,讓我們更深入 JS 的 Function。

const foo1 = (x, y, z) => x + y + z
console.log(
    foo1.name, // foo1
    foo1.length // 3
)

const foo2 = (...args) => console.log(args)
console.log(
    foo2.name, // foo2
    foo2.length // 0
)

const foo3 = foo1.bind(null, 1, 2)
console.log(
    foo3.name, // bound foo1
    foo3.length // 1
)

const foo4 = foo3.bind(null, 3, 4)
console.log(
    foo4.name, // bound bound foo1
    foo4.length // 0
)

觀察這段程式碼會發現:

  • Function.name
    Function 的名子
  • Function.length
    Function 尚缺的參數數量,最小為零, ...args 不被列入計算。
  • Function.prototype.bind
    給 Function 參數,並回傳一個新的 Function,新的 Function.name 會多加上 bound 。

藉此我們可以實作出真正的 Curry 。

const curry = func =>
    (...args) => {
        if (func.length <= args.length) {
            // 當目前 func 需要的參數 <= 傳入的參數
            return func.apply(null, args)
        } else {
            // 當參數不足,回傳新的 Curry
            return curry(func.bind(null, ...args))
        }
    }

const add = curry((x, y) => x + y)

console.log(
	add(2), // y => 2 + y
	add(2)(3), // 5
	add(2, 3) // 5
)

太完美了!而且它可以加工任何函數!
來試試看一個真正 Curry 的 Map。

const map = curry((func, array) => {
    if (array.length == 0) {
        return []
    } else {
        const [x, ...xs] = array
        return [func(x), ...map(func, xs)]
    }
})

console.log(
	map(x => x + 1, [1, 2, 3]), // [2, 3, 4]
	map(x => x + 1)([1, 2, 3]) // [2, 3, 4]
)

練習改寫先前寫的 Higher order Funtion 吧!
如果你完全懂的目前所有概念,這應該是件輕鬆的事。

Type Signature

在純 FP 語言中, 類型簽名(Type Signature) 編譯時會做 Type Check ,同時 Type Signature 可以讓人 快速了解 Funtion 的目的和行為 ,我們來看看這段程式碼。

// 函數名稱 :: 參數 -> 回傳值
// 在此 a 沒有限定類型
// head :: [a] -> a
const head = ([x, ...xs]) => x

就算看不懂 head 的程式碼,也可以看出 傳入一個 Array ,回傳一個 element ,從 head 的語意猜應該是回傳 Array[0]

Type Signature 在 FP 扮演舉足輕重的地位,雖然現在不會做 Type Check ( JS 並沒有 Type System ),但還是能 大幅增加可讀性,甚至可以用 Type Signature 做搜尋

Type Signature 也可以幫住我們了解、推演 Function 的運作規則。

// 在 :: 、 => 之間,為 類型約束(Type Constraints)
// 在此 a 的類型為 Num
// add :: Num a => a -> a -> a
const add = curry((x, y) => x + y)

// add2 :: Num a => a -> a
const add2 = add(2)

// five :: Num a => a
const five = add2(5)

// Six :: Num a => a
const Six = add(3)(3)

a -> a -> a 表示 傳入兩個 Num ,回傳一個 Num 的 Function ,
當傳入一個 Num 後, add 去掉了 a -> ,成了 a -> a (需要傳入一個 Num 的 Funtion ),
如果直接傳入兩個 Num , Six 去掉了 a -> a ->,成了 a (數字)。

// map :: (a -> b) -> [a] -> [b]
const map = curry((func, array) => array.map(func))

map 傳入的第一個參數 (a -> b) 即是一個 傳入 a ,回傳 b 的 Function ,
然後吃下 [a] 後會回傳 [b] ,有 a 有 b 表示 a 與 b 可能是不同 Type

Type Signature 就是如此簡單又強大,在 Hoogle (Haksell's dictionary)(https://www.haskell.org/hoogle/)Ramda Document(http://ramdajs.com/docs/) 隨處可見,當你知道咒語了,了解魔法就不是件難事,不過這需要大量的練習就是了。

改變輸入的順序

我相信 add 不能滿足我們了,現在我們要來點 subtract

const substract = curry((x, y) => x - y)
console.log(
	substract(8), // y = 8 - y
	substract(8)(7), // 1
	substract(8, 7) // 1
)

但如果我需要的是 x = x - 8 ,我要把 8 傳進 y 的位置,這狀況有點尷尬,或許我需要一個 交換前兩位輸入位置的 Function。

const flip = func => 
    curry((y, x, ...args) => func(x, y, ...args))

const somethingSubstract8 = flip(substract)(8)

這就是最簡單的解決方法,用一個 Lambda 改變參數傳入順序,其中交換前兩位的 flip 特別常用,所以這個函數通常是內建的。

而在 Ramda.js 中有個特別的解決方案,可以傳入 __ (double underscore) 佔個位置,然後下次執行時將 __ 替換掉。

const foo = curry(
    (a, b, c, d) => console.log(`[${a}, ${b}, ${c}, ${d}]`)
)

foo(__,1,2,3)(4) // [4, 1, 2, 3]
foo(__,1,2,__)(__,3)(4)// [4, 1, 2, 3] 

為此需要改寫 curry 的實作:

  • 將 __ 替換成新的參數
  • 判定參數數量是否足夠實行
const __ = {
    toString:_=>"Curry Placeholder"
}
Object.freeze(__)

const curry = func =>
    (acc,...args)=>{
        // 頭很痛
    }

基本想法的雛型︰

  • 用 acc 儲存結果。
  • 替換 __
    1. 迭代 old Args ,
      如果是 __ ,儲存 new Arg ,
      如果不是,儲存 old Arg ,
    2. 當沒有 old Args ,且有剩下 new Args , acc.concat(剩下 new Args) 。
  • 判斷是否執行
    func.length <= 不包含__的參數.length
const curry = func => {
	const replacePlaceholder = (old, args, acc = []) => {
		if (old.length == 0) {
			// 終止條件
			return [...acc, ...args]
		} else {
			const [x, ...xs] = old
			if (x === __) {
				const [y, ...ys] = args
				return replacePlaceholder(xs, ys, [...acc, y])
			} else {
				return replacePlaceholder(xs, args, [...acc, x])
			}
		}
	}

    const continueCurry = (old, ...args) => {
		const now = replacePlaceholder(old, args)
		// 不包含 __ 的參數數量
		const { length } = now.filter(x => x !== __)

		if (func.length <= length) {
			// 執行
			return func.apply(null, now)
		} else {
			// 儲存新參數
			return continueCurry.bind(null, now)
		}
	}
	// 第一次執行
	return continueCurry.bind(null, [])
}

完成,我們的手工 Ramda 又更完美了!

其實部份純 FP 語言當中也有類似的用法,在 Haskell 好像沒有,在我剛確認過在 PureScript 中有這個語法,之後我們再說吧。

後記

卡一下,好多人留言好溫暖好感動,謝謝你們。

參考資料


上一篇
Higher order Function = { Reduce } 與 應用實例
下一篇
Higher order Function = { Compose } 與 如何處理 Promise 、 Object
系列文
30天快樂學習 Functional Programming14
0
Kuro Hsu
iT邦新手 4 級 ‧ 2017-12-21 16:11:26

挺住啊,卡文就跟卡債一樣會越滾越大 /images/emoticon/emoticon69.gif

0
Xuan
iT邦新手 5 級 ‧ 2017-12-21 16:28:33

加油!

0
taiansu
iT邦新手 5 級 ‧ 2017-12-21 23:22:47

加油!墊檔的話,裝個 Ramda.js,教大家怎麼 map over object 也許是個方向?

0
konekoya
iT邦新手 5 級 ‧ 2017-12-22 07:13:19

保重啊

我要留言

立即登入留言