怎樣理解Haskell中的High Order Function？

01-06

如題，最近在學Haskell，在Edx上看lecture，先前還是比較順利的，然後學到了High Order Function，接觸到foldr、foldl這些之後腦袋一下子就轉不過來了，請問有什麼比較好的方法可以理解這種東西。
另外，從foldr、foldl開始，我漸漸感覺有點吃力，請問這對於將C/C++作為第一門語言的程序員來說是正常的現象嗎？

正規地講，一個以函數作為參數或者返回函數為結果的函數被稱為高階函數。而在實踐中，術語「柯里化」已經表達了返回函數作為結果的意思，所以高階函數常常僅僅指以函數作為參數的情形，否則Haskell里的函數基本都是高階函數了。以函數為參數的函數常常是其他多個函數更為一般的表達。比如定義把列表中所有元素都加1的函數：

plus1 :: [Int] -&> [Int] plus1 [] = [] plus1 (x:xs) = ((+1) x) : plus1 xs

把所有列表元素都取非的函數

nots :: [Bool] -&> [Bool] nots [] = [] nots (x:xs) = not x : nots xs

顯然是有公共部分的。我們來寫一下這些公共的部分

map [] = [] map (x:xs) = f x : map xs

其中f需要被定義，因為現在他是自由變數，f就是兩個函數不同的部分。可以在map中把f作為參數引入。就有

map f [] = [] map f (x:xs) = f x : map f xs

於是乎nots與plus1就可以用map定義

plus1 = map (+1) nots = map not

map函數的類型很明顯，他是總結前面nots、plus1的更為一般的函數。對於foldr函數，也是一樣的道理：

sum, product :: Num a =&> [a] -&> a sum [] = 0 sum (x:xs) = x + sum xs


product [] = 1

product (x:xs) = x * product xs
and,or :: [Bool] -&> Bool

and [] = True

and (x:xs) = x  and xs

or [] = False or (x:xs) = x || or xs

把公共的部分寫出來，列表為空時得一個特殊值e，不為空時則需要應用一個函數：

foldr [] = e foldr (x:xs) = x `f` foldr xs

e與f是自由的，需要作為參數引入，先引入e

foldr e [] = e foldr e (x:xs) = x `f` foldr e xs

再引入f

foldr f e [] = [] foldr f e (x:xs) = x `f` foldr f e xs

同理，上面的一堆函數就可以用foldr來定義了

sum xs = foldr (+) 0 xs ==eta化簡==&> sum = foldr (+) 0 product = foldr (*) 1 and = foldr () True ...

上面的一堆函數除了e與這個f外其餘部分都相同。只要變成參數引入進來就行了。

去看Structure and Interpretation of Computer Programs，第一章搞懂就行，然後回來繼續。

是正常現象。

Real World Haskell 裏有 foldr/foldl 的簡單實現。你給它喂一些參數然後親手展開看效果就可以了。

foldr :: (a -&> b -&> b) -&> b -&> [a] -&> b foldr step zero (x:xs) = step x (foldr step zero xs) foldr _ zero [] = zero

foldl :: (a -&> b -&> a) -&> a -&> [b] -&> a foldl step zero (x:xs) = foldl step (step zero x) xs foldl _ zero [] = zero

Chapter 4. Functional programming

或者看 GHC 的：

-- | "foldl", applied to a binary operator, a starting value (typically -- the left-identity of the operator), and a list, reduces the list -- using the binary operator, from left to right: -- -- &> foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn -- -- The list must be finite.


-- We write foldl as a non-recursive thing, so that it

-- can be inlined, and then (often) strictness-analysed,

-- and hence the classic space leak on foldl (+) 0 xs
foldl        :: (b -&> a -&> b) -&> b -&> [a] -&> b
foldl f z0 xs0 = lgo z0 xs0

             where

                lgo z []     =  z

                lgo z (x:xs) = lgo (f z x) xs
-- | "foldr", applied to a binary operator, a starting value (typically

-- the right-identity of the operator), and a list, reduces the list

-- using the binary operator, from right to left:

--

-- &> foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

foldr :: (a -&> b -&> b) -&> b -&> [a] -&> b -- foldr _ z [] = z -- foldr f z (x:xs) = f x (foldr f z xs) {-# INLINE [0] foldr #-} -- Inline only in the final stage, after the foldr/cons rule has had a chance -- Also note that we inline it when it has *two* parameters, which are the -- ones we are keen about specialising! foldr k z = go where go [] = z go (y:ys) = y `k` go ys

foldl: GHC/List.lhs

foldr: https://hackage.haskell.org/package/base-4.7.0.2/docs/src/GHC-Base.html

另，GitHub 上的 bitemyapp/learnhaskell · GitHub 項目推薦了這個視頻，我還沒看不過且先貼這：Tony Morris - Explain List Folds to Yourself

high order function的概念是普遍存在於FP中的，這對於習慣於命令式編程語言的人來說是有些難以理解。

關鍵就在於要理解function也是一級公民，和其他的數據類型一樣，也可以作為參數賦給函數，和C++中的函數作為參數的區別在於，C++中給的是函數的地址，也就是這個參數是一個「指針」，而FP中從本質上來說是把這個function本身去賦值。

借用 @閱千人而惜知己的一句話，一個以函數作為參數或者返回函數為結果的函數被稱為高階函數。當我們考慮以函數作為參數的高階函數情形時，往往是建立了一種抽象結構，而這些抽象結構的具體化就是靠輸入的函數參數了。

以foldr為例（foldl是類似的）。該函數的功能是是給定一個初始值z和一個函數f，將列表[a]中的值從最右邊開始逐個合併(reduce)為一個值，函數f是reduce時將累加值和列表元素合併的二元操作函數。因此foldr的類型簽名和實現是：

foldr :: (a -&> b -&> b) -&> b -&> [a] -&> b foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs)

該函數建立了如下圖右邊所示的抽象結構：

上圖左邊是列表[a]的代數結構，右邊的任意一個抽象結構都可以從左邊的結構中通過函數foldr f z來得到（因此左邊的列表[a]結構也稱為free monoid）。而函數foldr f z是由高階函數foldr和函數參數f、參數z一起得到的。函數foldr建立了一個通用的抽象結構，給其提供兩個具體的參數後就成為了一個將列表[a]結構變換為特定抽象結構的函數foldr f z。

比如我們提供函數(+)和0這兩個參數給foldr，就得到了函數foldr (+) 0，這就是函數sum，對列表[a]進行求和。提供函數(*)和1則得到foldr (*) 1，是函數product，對列表[a]進行求積。

簡單但不是很恰當的比喻是可以將高階函數看成可以接受C和C++的函數指針這樣的參數的函數。

另外，Haskell中的函數的類型簽名是非常重要的，雖然很多時候不用寫出來，但你在實現一個函數時一定要很清楚這個函數的類型。這樣在實現一個函數的代碼時才不容易出錯，也能更好的獲得提示。函數的類型簽名好象提出一個命題，實現這個函數的過程就象證明這個命題的過程，利用ghc的type hole功能，有時可以通過類型簽名的約束來推理出代碼的實現。

函數作為參數在C++的STL裡面不也是非常常見的事情么？

這現象很正常，我剛從 C 換到 Lisp 時間也這樣，多寫寫習慣那個思維方式就好了

正常現象，我建議你去看看相關的專業書籍（不是編程方面的！）否則後面的一堆概念你就都不懂了-&>_-&>

如果理解抽象的東西遇到困難，可以嘗試通過增強感性認識來尋求突破。

而增強感性認識的一大通途就是實踐。

去 https://projecteuler.net 用 Haskell 解至少 30 道題，把你一知半解的知識盡量用上，應該就會很有收穫了。起碼 map，compose，fold* 這些，熟練使用應該問題不大。

不就給函數傳個函數嘛。

高階函數就是以函數為參數或返回值的函數

類比來看，高階導數就是導數的導數

高次冪就是冪的冪

高階函數就是函數的函數

這種情況很正常。因為命令式和函數式差別很大。多寫寫情況就會改善，那時就容易理解了。