Fold

所謂 Fold 就是來簡化我們在遞迴中很常遇到的模式，匹配 (x:xs) 將 x 取出來後繼續將 xs 放入 function 運算 直到 [] 。通常會是傳入一個需要兩個參數的函數、初始值、需要處理的 List 。
而二元函數中的第一個參數會是累加值，第二個則會是現在丟進來的元素，然後回傳值會是下一次的累加值，以此形式不斷執行直到 List 跑完。

Array.reduce 就是運用到這個概念

首先是 foldl 又稱為左折疊，也就是它是從 List 的左邊開始不斷向右迭代

:t foldl -- foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

我們來用 foldl 實作一個簡單的 function ，用途是累加 List 中所有的元素。

sum' :: (Num a) => [a] -> a  
sum' xs = foldl (\acc x -> acc + x) 0 xs

sum' [4,2,3,1,2,2] -- 14

(\ acc x → acc +x) 是一個二元函數，0 是初始值， xs 則是要折疊的 List，

第一次迴圈時 acc 會是初始值也就是 0 ， x 則會是第一個元素也就是 4 ，兩個相加後是 4 ，第二次迴圈時 acc 就會是 4 同時 x 會是 2，第三次遞迴時 acc 就會是 6 ，x 會是 3 。
以此類推最後會輸出 14

接下來是 foldr 其實就跟 foldl 很像只是方向是從右邊開始，在大多數時候他們很像

:t foldr foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

sum'' :: (Num a) => [a] -> a  
sum'' xs = foldr (\x acc -> acc + x) 0 xs

sum'' [4,2,3,1,2,2] -- 14

先稱呼 (\x acc -> acc + x) 為 f
foldl 執行過程會像是 f(f(f(f(f(f(4 0)2)3)1)2)2) foldr 執行過程會像是 f(f(f(f(f(f(2 0)2)1)3)2)4)

稍微理解折疊的奧妙後我們來重寫原生就有提供的 reverse function

reverse [1,2,3] -- [3,2,1]

reverse' :: [a] -> [a]  
reverse' = foldl (\acc x -> x : acc) []

reverse' [1,2,3] -- [3,2,1]

過程會是

1. 1 : []
2. 2 : [1]
3. 3 : [2,1]
4. [3,2,1]

Haskell 還有提供其他好用的 function 像是 foldl1 、 foldr1 、scanl 、scanr

foldl1 及foldr1 就跟 foldl 和 foldr 類似只是不用提供初始值，而是會把 List 的頭或者尾（左折疊就是頭，右折疊就是尾）當作初始值。

foldl1 (\acc x -> acc + x) [1..5] -- 15
foldr1 (\x acc -> acc + x) [1..5] -- 15

而 scan 的概念就跟 fold 很像，只是會把每一次的累加值都丟進 List

scanl (\acc x -> acc + x) 0 [1..5] -- [0,1,3,6,10,15]
scanr (\x acc -> acc + x) 0 [1..5] -- [15,14,12,9,5,0]

而 scanl 最後一個元素就會是用 foldl 的最後結果，而 scanr 第一個元素就會是 foldr 的最後結果

$ 函數呼叫

$ 稱為函數呼叫符

:t ($) -- ($) :: (a -> b) -> a -> b

首先我們先想想一個可以傳入三個參數的函數， f a b c 他是左向右結合，實際上他的執行順序是 ((f a )b)c 而使用 $ 則會是從右向左。

所以像之前的 print (map (+1) [1,2,3,4])就可以改寫成 print $ map (+1) [1,2,3,4,5]簡單來說可以減少許多括號的產生。

這個 function 是將 1 到 10 都加 3 後，並把3的倍數濾掉最後全部相加的 function

foldl1 (+) ( filter (\x -> x `mod` 3 == 0) (map (+3) [1..10]))

foldl1 (+) (filter (\x -> x mod 3 == 0) (map (+3) [1..10])) 可以想成 f (g (z x)) 那就跟 f $ g $ z x 等價。

也就是我們能把 function 改寫為

foldl1 (+) $ filter (\x -> x `mod` 3 == 0) $ map (+3) [1..10]

Function composition

在數學上 function composition （合成函數），是先執行一個函數並將他的輸出作為另外一個函數的輸入進而產生一個新的函數。

在 Haskell 提供一個 function 來幫助我們達成這件事情 .

:t (.) -- (.) :: (b -> c) -> (a -> b) -> a -> c

他的型別已經告訴我們他是先傳入兩個 function (b -> c) 及 (a -> b ) 然後將 a 傳入 (a -> b) 然後會先得出 b 在丟進 (b -> c) 得出 c

很像數學上的 (f ∘ g)(x) = f(g(x)) 所以 f . g 就是 f (g x)

add5:: Num a => a -> a
add5 = (+5)

squere:: Num a => a -> a
squere = (^2)

substract4:: Num a => a -> a
substract4 = subtract 4

print $ map (\x -> substract4 (squere (add5 x))) [1 .. 5]
print $ map (substract4 . squere . add5) [1 .. 5]

可以看出來我們可以變得更加簡單地組合這些 function

這種可以簡略參數的形式又稱為 point free style，至於可讀性就見仁見智了。

這幾天算是把 higher order function 這個在 Haskell 及 FP 裡都相當重要的概念介紹了一遍。

就我自己的經驗來說就算是在寫 js 只要能多加運用 higher order function 及 curried function 就能把程式碼寫得相當工整。

但老話一句，好不好閱讀真的看人。畢竟我有被同事抱怨過可不可以不要一直 .map 串 .filter （那次好像串了四五個。），也被抱怨過不要寫 curried function 因為看不懂為什麼這個 function 可以 work。

今天的程式碼：

https://github.com/toddLiao469469/30days-for-haskell