Haskell/高階函數和Currying
高階函數是一類可以接受函數為參數的函數。我們看到過的有 map
，沒什麼多大的不同。他們提供了一種只有函數式編程語言才有的抽象能力。在Haskell這樣的函數式編程語言中，函數和其他成員一樣，要理解高階函數並不難。
本書中有獨立的一章是關於高階函數的，這不是因為他們很難——我們也已經認識它們了——而是因為它們很強大。一旦我們可以像把函數作為參數來調用，函數就可以變得更加強大。一般來說，高階函數有很高的抽象能力 。 另外,高階函數使得Haskell 更加有趣。
最快的快排算法 編輯
不要太激動，但 快排 quickSort
的確是最快的。假如你已經聽過了可以跳過。
quickSort
的背後
編輯
很簡單，對於一個表，我們先取其第一個元素，再把這個表分成三部分。
第一部分是那些應該排在這個元素之前的元素，第二部分是那些等於這個元素的元素，第三部分是那些應該排在這個元素之後的元素。然後呢，當然是要把這三部分連接起來。我們就得到了一個更「好」的表，不是嗎？
注意，第一部分和第三部分都是沒有排好序的；至於第二部分，就根本不需要排序（因為它們都是相等的）；接下來我們應該把第一和第三部分排好序，如何？要這麼排呢？只需要把相同的算法重新用一遍就行。但所有都完成後，這個表也排好了。
So Let's Get Down To It! 編輯
 空表，什么都不做
 这个是递归的初始条件
quickSort [] = []
 只有一个元素的时候，也不需要排序
 实际上，第三个已经包含这一部分的处理了
 但我们要一步一步来
quickSort [x] = [x]
 整个排序的关键
 拿出一个元素作为 “支点” ，剩下的去排序
 别忘了支点是在表的中间 ！
quickSort (x : xs) = (quickSort less) ++ (x : equal) ++ (quickSort more)
where less = filter (< x) xs
equal = filter (== x) xs
more = filter (> x) xs
完成了！ 我想你已經看過 quickSort
，你也許在想遞歸是很難實現奇技淫巧而已。
現在，我們要怎麼利用它 ？ 編輯
在我們的 quickSort
中，對任意表的排序都是小菜一碟。假設我們有一個 字符串( String
) 表,例如一堆英語單詞，我們也可以用現在的 quickSort
對其排序。 在剩下的章節李，我們會用一個偽字典來做例子。(當然，用 有25000 單詞的字典也是可以的）
dictionary = ["I", "have", "a", "thing", "for", "Linux"]
上面的就是給我們用的quickSort
字典
["I", "Linux", "a", "for", "have", "thing"]
假如我們要按降序排列那該怎樣做？很容易，把這個表翻轉就行了，reverse (quickSort dictionary)
就可以了。
等一下，翻轉並不能使得我們把這個表真正的按降序排列，我們只是把它按升序排列然後再翻轉而已。雖然這樣做結果是一樣，但是卻不是同一回事。
而且，結果可能並不是你想要的， 「a「 應該在 」I」 前，「Linux」 應該在 「have」 和 「thing」 之間。出了什麼問題呢？
是這樣的，字符全 (String
) 使用 ASCII 碼來表示的，而在 ASCII碼 （和其他幾乎所有的編碼方法）里，大寫字母是小於小寫字母的。所以，「Z」 小於 」a」 . 我們得修改一下代碼，使得 quickSort
忽略大小寫。可能以後有用。
但是，看上去 quickSort
已經加不了什麼了。我們得做點額外的東西。
修改我們原來的代碼 編輯
我們需要從 quickSort
中分離其對比的功能。
What we need to do is to factor out the comparisons quickSort
makes. We need to provide quickSort
with a function that compares two elements, and gives an Ordering
, and as you can imagine, an Ordering
is any of LT, EQ, GT
.
To sort in the descending order, we supply quickSort
with a function that returns the opposite of the usual Ordering
. For the caseinsensitive sort, we may need to define the function ourselves. By all means, we want to make quickSort
applicable to all such functions so that we don't end up writing it over and over again, each time with only minor changes.
quickSort
, Take Two
編輯
Our quickSort
will take two things this time: first, the comparison function, and second, the list to sort.
A comparison function will be a function that takes two things, say, x
and y
, and compares them. If x
is less than y
(according to the criteria we want to implement by this function), then the value will be LT
. If they are equal (well, equal with respect to the comparison, we want "Linux" and "linux" to be equal when we are dealing with the insensitive case), we will have EQ
. The remaining case gives us GT
(pronounced: greater than, for obvious reasons).
 no matter how we compare two things
 the first two equations should not change
 they need to accept the comparison function though
 but the result doesn't need it
quickSort _ [] = []
quickSort _ [x] = [x]
 we are in a more general setting now
 but the changes are worth it!
 c is the comparison function
quickSort c (x : xs) = (quickSort c less) ++ (x : equal) ++ (quickSort c more)
where less = filter (\y > y `c` x == LT) xs
equal = filter (\y > y `c` x == EQ) xs
more = filter (\y > y `c` x == GT) xs
Cool!
註解
Almost all the basic data types in Haskell are members of the 
But What Did We Gain? 編輯
Reuse. We can reuse quickSort
to serve different purposes.
 the usual ordering
 uses the compare function from the Ord class
usual = compare
 the descending ordering, note we flip the order of the arguments to compare
descending x y = compare y x
 the caseinsensitive version is left as an exercise!
insensitive = ...
 can you think of anything without making a very big list of all possible cases?
And we are done!
quickSort usual dictionary
should, then, give
["I", "Linux", "a", "for", "have", "thing"]
The comparison is just compare
from the Ord
class. This was our quickSort
, before the tweaking.
quickSort descending dictionary
now gives
["thing", "have", "for", "a", "Linux", "I"]
And finally,
quickSort insensitive dictionary
gives
["a", "for", "have", "I", "Linux", "thing"]
Exactly what we wanted!
練習 

Write insensitive , such that quickSort insensitive dictionary gives ["a", "for", "have", "I", "Linux", "thing"] 
HigherOrder Functions and Types 編輯
Our quickSort
has type (a > a > Ordering) > [a] > [a]
.
Most of the time, the type of a higherorder function provides a good guideline about how to use it. A straightforward way of reading the type signature would be, "quickSort
takes a function that gives an ordering of a
s, and a list of a
s, to give a list of a
s". It is then natural to guess that the function sorts the list respecting the given ordering function.
Note that the parentheses surrounding a > a > Ordering
is mandatory. It says that a > a > Ordering
altogether form a single argument, an argument that happens to be a function. What happens if we omit the parentheses? We would get a function of type a > a > Ordering > [a] > [a]
, which accepts four arguments instead of the desired two (a > a > Ordering
and [a]
). Furthermore none of the four arguments, neither a
nor Ordering
nor [a]
are functions, so omitting the parentheses would give us something that isn't a higher order function.
Furthermore, it's worth noting that the >
operator is rightassociative, which means that a > a > Ordering > [a] > [a]
means the same thing as a > (a > (Ordering > ([a] > [a])))
. We really must insist that the a > a > Ordering
be clumped together by writing those parentheses... but wait... if >
is rightassociative, wouldn't that mean that the correct signature (a > a > Ordering) > [a] > [a]
actually means... (a > a > Ordering) > ([a] > [a])
?
Is that really what we want?
If you think about it, we're trying to build a function that takes two arguments, a function and a list, returning a list. Instead, what this type signature is telling us is that our function takes one argument (a function) and returns another function. That is profoundly odd... but if you're lucky, it might also strike you as being profoundly beautiful. Functions in multiple arguments are fundamentally the same thing as functions that take one argument and give another function back. It's OK if you're not entirely convinced. We'll go into a little bit more detail below and then show how something like this can be turned to our advantage.
練習 

The following exercise combines what you have learned about higher order functions, recursion and IO. We are going to recreate what programmers from more popular languages call a "for loop". Implement a function for :: a > (a>Bool) > (a>a) > (a> IO ()) > IO () for i p f job =  ???An example of how this function would be used might be for 1 (<10) (+1) (print)which prints the numbers 1 to 9 on the screen. Starting from an initial value
Some more challenging exercises you could try

Currying 編輯
I hope you followed the reasoning of the preceding chapter closely enough. If you haven't, you should, so give it another try.
Currying is a technique^{[1]} that lets you partially apply a multiparameter function. When you do that, it remembers those given values, and waits for the remaining parameters.
Our quickSort
takes two parameters, the comparison function, and the list. We can, by currying, construct variations of quickSort
with a given comparison function. The variation just "remembers" the specific comparison, so you can apply it to the list, and it will sort the list using the that comparison function.
descendingSort = quickSort descending
What is the type of descendingSort? quickSort
was (a > a > Ordering) > [a] > [a]
, and the comparison function descending
was a > a > Ordering
. Applying quickSort
to descending
(that is, applying it partially, we haven't specified the list in the definition) we get a function (our descendingSort
) for which the first parameter is already given, so you can scratch that type out from the type of quickSort
, and we are left with a simple [a] > [a]
. So we can apply this one to a list right away!
descendingSort dictionary
gives us
["thing", "have", "for", "a", "Linux", "I"]
It's rather neat. But is it useful? You bet it is. It is particularly useful as sections, you might notice. Currying often makes Haskell programs very concise. More than that, it often makes your intentions a lot clearer. Remember
less = filter (< x) xs
from the first version of quickSort
? You can read it aloud like "keep those in xs
that are less than x
". Although (< x)
is just a shorthand for (\y > y < x)
, try reading that aloud!
Notes 編輯
 ↑ named after the outstanding logician Haskell Brooks Curry, the same guy after whom the language is named.
參見 編輯
高階函數和Currying 
習題解答 
Elementary Haskell 
Haskell 
Haskell基礎
>> 初級Haskell
>> Haskell進階
>> Monads
