Haskell/高阶函数和Currying

高阶函数和Currying (解答)

Elementary Haskell

高阶函数是一类可以接受函数为参数的函数。我们看到过的有 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 case-insensitive 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 Ord class. This class defines an ordering, the "natural" one. The functions (or, operators, in this case) (<), (==) or (>) provide shortcuts to the compare function each type defines. When we want to use the natural ordering as defined by the types themselves, the above code can be written using those operators, as we did last time. In fact, that makes for much clearer style; however, we wrote it the long way just to make the relationship between sorting and comparing more evident.

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 case-insensitive 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"]`

Higher-Order Functions and Types

Our quickSort has type (a -> a -> Ordering) -> [a] -> [a].

Most of the time, the type of a higher-order 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 as, and a list of as, to give a list of as". 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 right-associative, 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 right-associative, 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 i, the for executes job i. It then modifies this value f i and checks to see if the modified value satisfies some condition. If it doesn't, it stops; otherwise, the for loop continues, using the modified f i in place of i.

The paragraph above gives an imperative description of the for loop. What would a more functional description be?
Implement the for loop in Haskell.
Why does Haskell not have a for loop as part of the language, or in the standard library?

Some more challenging exercises you could try

What would be a more Haskell-like way of performing a task like 'print the list of numbers from 1 to 10'? Are there any problems with your solution?
Implement a function sequenceIO :: [IO a] -> IO [a]. Given a list of actions, this function runs each of the actions in order and returns all their results as a list.
Implement a function mapIO :: (a -> IO b) -> [a] -> IO [b] which given a function of type a -> IO b and a list of type [a], runs that action on each item in the list, and returns the results.

This exercise was inspired from a blog post by osfameron. No peeking!

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 multi-parameter 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!