我理解您的问题更确切地是:“如果我已经使用诸如C或Java之类的命令式语言进行编程,那么我如何为函数式编程调整思维?” 以您的问题为例,我将在周六上午详细回答这个问题。我将追踪一个函数式程序员的演变,分为三个阶段,每个阶段都是越来越高级的境界 - 1)迭代思考;2)递归思考;和3)惰性思考。
第一部分 - 迭代思考
假设我正在使用C进行编程,并且不能或不想使用递归 - 可能编译器无法优化尾递归,递归解决方案会导致堆栈溢出。因此,我开始思考需要维护哪些状态。我想象一个小机器爬过输入。它记住它是在搜索递增还是递减序列。如果它还没有决定,它会根据当前输入进行决策,如果可以的话。如果它发现输入朝着错误的方向前进,则以zigzag = true终止。如果它到达输入的结尾,则以zigzag = false终止。
int
zigzag(int *data, int n)
{
enum {unknown, increasing, decreasing} direction = unknown;
int i;
for (i = 1; i < n; ++i)
{
if (data[i] > data[i - 1]) {
if (direction == decreasing) return 1;
direction = increasing;
}
if (data[i] < data[i - 1]) {
if (direction == increasing) return 1;
direction = decreasing;
}
}
return 0;
}
这个程序典型的C程序:它高效但很难证明它会做正确的事情。即使对于这个简单的例子,也不是立刻显而易见的,它不能陷入无限循环,或者在逻辑上走错路。当然,对于更复杂的程序来说情况会更糟。
第二部分 - 递归思考
我发现编写可读性强的程序,遵循函数式语言的精神(而不只是试图将命令式解决方案转化为该语言)的关键是专注于程序应计算的“内容”而不是“如何”计算。如果你能够以足够精度这样做-如果你能清晰地写出问题-那么在函数式编程中,大多数时间你几乎已经得到了解决方案!
因此,让我们首先更详细地写出要计算的内容。我们想知道一个列表是否呈之字形(即在某个点下降,在另一个点上升)。哪些列表符合这个标准?好吧,如果一个列表呈之字形,则:
- 长度大于2且
- 一开始递增,但在某个时刻开始递减 或
- 一开始递减,但在某个时刻开始递增 或
- 其尾部呈锯齿状。
可以将上述语句直接或多或少地翻译成Scheme函数:
(define (zigzag xs)
(and (> (length xs) 2)
(or (and (initially-increasing xs) (decreases xs))
(and (initially-decreasing xs) (increases xs))
(zigzag (cdr xs)))))
现在我们需要定义“initially-increasing”、“initially-decreasing”、“decreases”和“increases”。 “initially-”函数足够简单:
(define (initially-increasing xs)
(> (cadr xs) (car xs)))
(define (initially-decreasing xs)
(< (cadr xs) (car xs)))
那么decreases
和increases
呢?如果一个序列长度大于1且第一个元素大于第二个元素,或者它的尾部减少,则该序列减少:
(define (decreases xs)
(letrec ((passes
(lambda (prev rest)
(cond ((null? rest) #f)
((< (car rest) prev)
#t)
(else (passes (car rest) (cdr rest)))))))
(passes (car xs) (cdr xs))))
我们可以编写一个类似的
increases
函数,但很明显只需要进行一次更改:
<
必须变成
>
。复制这么多代码应该会让你感到不安。我能不能要求语言为我创建一个像
decreases
这样的函数,但是在那个位置使用
>
呢?在函数式语言中,你可以完全做到这一点,因为
函数可以返回其他函数!因此,我们可以编写一个函数来实现:"给定一个比较运算符,返回一个函数,如果它的参数的任何两个连续元素之间的比较为真,则返回真"。
(define (ever op)
(lambda (xs)
(letrec ((passes
(lambda (prev rest)
(cond ((null? rest) #f)
((op (car rest) prev)
#t)
(else (passes (car rest) (cdr rest)))))))
(passes (car xs) (cdr xs)))))
增加
和减少
现在都可以非常简单地定义:
(define decreases (ever <))
(define increases (ever >))
没有更多的功能需要实现了 - 我们完成了。与C版本相比,这个版本的优点是显而易见的 - 它要容易得多,可以理解这个程序会做正确的事情。这个程序的大部分都很琐碎,所有的复杂性都被推到了
ever
函数中,它是一个非常通用的操作,在许多其他上下文中也会很有用。我相信通过搜索,人们可以找到一个标准(因此更可靠)的实现,而不是这个定制的实现。
虽然这是一种改进,但这个程序仍然不完美。有很多自定义递归,一开始并不明显所有的递归都是
尾递归(尽管确实如此)。此外,该程序保留了C语言的模糊回声,以多个条件分支和退出点的形式存在。我们可以通过使用
惰性求值来获得更清晰的实现,为此我们将切换语言。
第三部分 - 惰性思考
让我们回到问题定义。它可以比第二部分中更简单地陈述为:“如果序列包含相邻元素之间的比较,这些比较在两个方向上进行,则该序列会呈现锯齿状(即非排序)。我可以将这句话直接或多或少地翻译成Haskell代码:
zigzag xs = LT `elem` comparisons && GT `elem` comparisons
现在我需要一种方法来推导“比较”(
comparisons
),即列表中每个成员与其后继的比较。这并不难做,最好通过示例来解释。
> xs
[1,1,1,2,3,4,5,3,9,9]
> zip xs (tail xs)
[(1,1),(1,1),(1,2),(2,3),(3,4),(4,5),(5,3),(3,9),(9,9)]
> map (\(x,y) -> compare x y) $ zip xs (tail xs)
[EQ,EQ,LT,LT,LT,LT,GT,LT,EQ]
这就是我们所需要的,这两行代码就是完整的实现 -
zigzag xs = LT `elem` comparisons && GT `elem` comparisons
where comparisons = map (\(x,y) -> compare x y) $ zip xs (tail xs)
我要指出的是,该程序只需通过一次列表来测试递增和递减的情况。
现在你可能想到了一个异议: 这种方法难道不浪费吗?它不是要搜索整个输入列表,而只需要到第一个方向改变处吗?实际上,不是这样的,因为有惰性求值。在上面的示例中,它计算了整个比较列表,因为必须将其打印出来。但如果它将结果传递给zigzag
,它只会评估足以找到一个GT
实例和一个LT
实例的比较列表,而不再往下执行。为了使自己相信这一点,请考虑以下情况:
> zigzag $ 2:[1..]
True
> zigzag 1:[9,8..]
True
这两种情况下的输入都是无限列表([2,1,2,3,4,5..]和[1,9,8,7,6,5...])。尝试将它们打印出来,它们会填满屏幕。但将它们传递给zigzag
,它将很快返回,一旦发现方向改变。
阅读代码时的许多困难来自于跟踪多个控制流分支。而其中许多分支实际上是为了避免计算我们不需要的部分。但是使用惰性评估可以实现同样的效果,使程序更短且更符合原始问题。
let
的一个原因是你只能对给定符号进行一次define
,而let
可以暂时覆盖现有的define
。在小程序中,您总是可以知道哪些符号已经有定义,并且可以证明使用define是安全的。在稍微大一点的程序中,最安全的方法通常是使用let
(以及它的朋友let*
和letrec
)来创建适当范围的临时定义。 - sblom