《Two Dozen Short Lessons in Haskell》学习（十四）- Truncating Sequences and Lazy Evaluation

《Two Dozen Short Lessons in Haskell》(Copyright © 1995, 1996, 1997 by Rex Page，有人翻译为Haskell二十四学时教程，该书如果不用于赢利，可以任意发布，但需要保留他们的copyright)这本书是学习 Haskell的一套练习册，共有2本，一本是问题，一本是答案，分为24个章节。在这个站点有PDF文件。几年前刚开始学习Haskell的时候，感觉前几章还可以看下去，后面的内容越来越难以理解。现在对函数式编程有了一些了解后，再来看这些题，许多内容变得简单起来了。

初学Haskell之前一定要记住：

把你以前学习面向过程的常规的编程语言，如Pascal、C、Fortran等等统统忘在脑后，函数式编程完全是不一样的编程模型，用以前的术语和思维来理解函数式编程里的概念，只会让你困惑和迷茫，会严重地影响你的学习进度。

这个学习材料内容太多，想把整书全面翻译下来非常困难，只有通过练习题将一些知识点串起来，详细学习Haskell还是先看其它一些入门书籍吧，这本书配套着学学还是不错的。

第十四章 截断序列和惰性求值

1 What is the value of w?

HASKELL DEFINITION • u, v, w :: String

HASKELL DEFINITION • u = "Four vier cuatro"

HASKELL DEFINITION • v = drop 5 u

HASKELL DEFINITION • w = drop 5 v

a "Four "

b "vier "

c "cuatro"

d "cinco"

2 What string does the following command deliver?

HASKELL COMMAND • takeWhile (/= blank) "Four score and seven"

a "score and seven"

b " score and seven"

c "Four "

d "Four"

3 What string does the following command deliver?

HASKELL COMMAND • dropWhile (/= blank) "Four score and seven"

a "score and seven"

b " score and seven"

c "Four "

d "Four"

4 What value does the following command deliver?

HASKELL DEFINITION • dozen = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ]

HASKELL COMMAND • [ take 2 xs | xs <- iterate (drop 2) dozen ]

a [1, 2, 3, 4, 5, 6]

b [ [1, 2], [3, 4], [5, 6], [7, 8], [9, 10], [11, 12], [ ], [ ], [ ], [ ], [ ], … ]

c [2, 4, 6, 8, 10, 12]

d [ [1, 2, 3, 4, 5, 6], [7, 8, 9, 10, 11, 12] ]

5 Which of the following formulas delivers the product of the numbers in the sequence xs?

a dropWhile (/= 0) (iterate (*) xs)

b takeWhile (/= 0) (iterate (*) xs)

c foldr (*) 0 xs

d foldr (*) 1 xs

6 Given the following definition, which of the formulas delivers the number 3?

HASKELL DEFINITION • k x y = x

HASKELL DEFINITION • first, second, third :: Integer

HASKELL DEFINITION • first = k (4-1) 0

HASKELL DEFINITION • second = k (1+2) "three"

HASKELL DEFINITION • third = k 3 (1 ‘div‘ 0)

a first

b second

c third

d all of the above

7 Consider the following function.

HASKELL DEFINITION • f :: String -> [String]

HASKELL DEFINITION • f w = [take 2 w, drop 2 w]

What does the formula iterate f "cs1323" deliver?

a [ "cs", "1323", [ ], [ ], …

b [ "cs", "13", "23", [ ], [ ], …

c [ ["cs"], ["1323"], [ ], [ ], …

d error … type mismatch

=========================================================

答

案

在

下

面

=========================================================

1 c

drop n list函数的功能就是把一个列表list中的前n个元素扔掉。

而take n list就是取列表list中的前n个元素。

drop 5 u为"vier cuatro"

drop 5 v就是"cuatro”

2 d

takeWhile cond list函数可以按面向过程的函数来理解。

从列表list中不停地取出元素，但一定要使条件cond为真，如果cond为假时，整个取出元素的过程就停止了。

本题中的函数会从"Four score and seven"中取出元素，但不能是空格(/= blank)，一旦遇到空格，就不再取元素了。

所以答案是"Four”

这里引入了惰性求值的概念：

haskell总是在最后一刻才进行求值计算，比如takeWhile (>3) [4, 5, 2, (3^1000) ]

会得到[4,5]

再评估第3个元素时，发现是2，小于3，评估的过程就结束了，返回了[4,5]结果，后面的(3^1000)就没有计算，不管它是一个多么复杂的表达式，甚至它被0除，都不会进行评估计算，这就是惰性求值。

这里的(>3)是个柯里函数形式，(>3) x与x>3是等价，不过后者我们看得更顺眼一些。

再看几个例子：

(== 0) x                x == 0

(< 0) x                 x < 0

(‘div‘ 10) x            x ‘div‘ 10

(c+) x                   c + x

(1-) x                   1 - x

3 b

与第2题有些类似，满足条件的都要从列表中扔掉，当条件不满足时，这个过程终止。

4 b

这道题有点难，要一步一步的分析：

iterate (drop 2) dozen是一个迭代方法，把函数(drop 2)先应用于列表dozen上，然后再不断地迭代应用于后续生成的结果上。

第一个元素是：[1,2,3,4,5,6,7,8,9,10,11,12]

第二个元素是：[3,4,5,6,7,8,9,10,11,12]

第三个元素是：[5,6,7,8,9,10,11,12]

......

以后还有无穷的元素：[]

所以iterate (drop 2) dozen的结果是一个无穷列表，即：

[ [1,2,3,4,5,6,7,8,9,10,11,12],

[3,4,5,6,7,8,9,10,11,12],

[5,6,7,8,9,10,11,12],

[7,8,9,10,11,12], 

[9,10,11,12],

[11,12],

[], [], ... ]

然后再对其中的每个元素应用函数take 2，也就是取前2个数据，就得到：

[[1,2], [3,4], [5,6], [7,8], [9,10], [11,12], [], [], ... ]

5 d

神奇的foldr函数，见《Two Dozen Short Lessons in Haskell》学习(十)中对这个函数的解释。

6 d

在这个函数third = k 3 (1 ‘div‘ 0) 中有一个惰性求值，(1 ‘div‘ 0) 这部分内容根本就没有计算。

7 d

iterate函数要求输入参数和输出函数是相同类型的，这样才能无限迭代下去。

如果函数f的类型是f :: String -> String，才可以进行无限调用。

所以会得到类型不匹配的错误。