我决定学习一些函数式语言，毕竟我迷上了 lisp-scheme。
我正在尝试创建一个函数来检查列表是否已排序，最低的第一个变得更高，反之亦然，如果它可以排序，它应该返回 true，否则返回 false。
这是我的第一个代码，仅在列表增加（或相等）时才有效。
(define sorted?
(lambda (lst)
(cond ((empty? lst) #t)
(else (and (<= (car lst) (cadr lst))
(sorted? (cdr lst)))))))
澄清：像 (sorted? '(1 2 3 4 5)) 和 (sorted? '(5 4 3 2 1)) 这样的东西应该返回 true，否则当然返回 false。
在以函数式编程时我应该如何思考？语法似乎直截了当，但我不习惯这种逻辑。
你几乎是对的，看：
(define sorted?
(lambda (lst)
(cond ((or (empty? lst) (empty? (cdr lst)))
#t)
(else (and (<= (car lst) (cadr lst))
(sorted? (cdr lst)))))))
在基本情况下稍作修改，一切就绪。当列表中只剩下一个元素时必须停止，否则cadr表达式会抛出错误。
对于您问题的第二部分：如果您想检查它是否使用不同的标准进行排序，只需将比较函数作为参数传递，如下所示：
(define sorted?
(lambda (lst cmp)
(cond ((or (empty? lst) (empty? (cdr lst)))
#t)
(else (and (cmp (car lst) (cadr lst))
(sorted? (cdr lst) cmp))))))
(sorted? '(1 2 3 4 5) <=)
> #t
(sorted? '(5 4 3 2 1) >=)
> #t
现在，如果您想知道列表是按升序还是降序排序：
(define lst '(1 2 3 4 5))
(or (sorted? lst >=) (sorted? lst <=))
> #t
如您所见，函数式编程是关于定义尽可能通用的过程并将它们组合起来以解决问题。您可以将函数作为参数传递这一事实有助于实现泛型函数。
具体实现
我会接受Óscar López 的回答并更进一步：
(define sorted? (lambda (lst)
(letrec ((sorted-cmp
(lambda (lst cmp)
(cond ((or (empty? lst) (empty? (cdr lst)))
#t)
(else (and (cmp (car lst) (cadr lst))
(sorted-cmp (cdr lst) cmp)))))))
(or (sorted-cmp lst <=) (sorted-cmp lst >=)))))
这个版本和他的最大区别是sorted?现在将 Óscar 的版本定义为一个内部辅助函数，使用letrec和调用它两种方式。
功能性思维
实际上，您选择了一个很好的示例来说明 Scheme 如何看待世界的某些方面，并且您的实现有了一个非常好的开始。
解决此问题的一个重要功能原则是，您可以放置的任何内容都(**here** more stuff '(1 2 3 4))可以作为参数传递给另一个函数。也就是说，函数是函数式编程语言中的第一类。因此，您在比较中使用的事实<=意味着您可以将<=其作为参数传递给另一个相应地进行比较的函数。Óscar 的回答很好地说明了这一点。
这个问题的另一个体现另一种常见功能模式的方面是主要由(cond)块组成的功能。在许多函数式编程语言（Haskell、ML、OCaml、F#、Mathematica）中，您获得的模式匹配能力比在 Scheme 默认情况下获得的要强。因此，(cond)在 Scheme 中，您必须描述如何测试您所寻求的模式，但这通常相当简单（例如(or (empty? lst) (empty? (cdr lst)))在这个 implementation.
我认为在这个问题中得到很好体现的最后一种函数式编程模式是，许多函数式编程解决方案都是递归的。递归是我必须使用letrec而不是普通的 ol' 的原因let。
通过对第一个元素（或本例中的 2 个元素）进行操作，然后在列表的尾部 ( ) 上重复操作，您几乎可以做任何事情cdr。命令for式while循环在 Scheme 中并非不可能（尽管它们在诸如 Haskell 之类的纯函数式语言中几乎是不可能的），但在许多情况下它们在 Scheme 中有点不合适。但是，Scheme 的灵活性允许您作为开发人员做出决定，从而在某些情况下实现重要的性能或可维护性优化。
继续探索
我在这里回答的第一个实现是根据它在列表中看到的内容sorted?来决定要传递给哪个比较运算符。sorted-cmp当我发现一个列表可以以两个相等的数字开头时，我放弃了这一点'(1 1 2 3 4 5)。但当我想得更多时，肯定有一种方法可以跟踪你是否已经决定了一个方向，因此，只需要一个电话就可以了sorted-cmp。你可以考虑下一个探索。
我将把你的问题理解为，更具体地说，“如果我已经使用 C 或 Java 等命令式语言进行编程，我该如何调整我的函数式编程思维？” 以你的问题为例，我将在周六早上用长篇回答这个问题。我将通过三个阶段来追踪函数式程序员的演变，每个阶段依次是更高的 zen - 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;
}
}
/* We've made it through the gauntlet, no zigzagging */
return 0;
}
这个程序是典型的 C 程序：它很高效，但很难证明它会做正确的事情。即使对于这个简单的示例，它也不能立即陷入无限循环，或者在某个地方出现错误的逻辑转向。当然，更复杂的程序会变得更糟。
我发现以函数式语言的精神编写可读程序的关键（而不是仅仅试图将命令式解决方案转变为该语言）是关注程序应该计算什么而不是它应该如何做。如果你能以足够的精度做到这一点——如果你能清楚地写出问题——那么在函数式编程的大部分时间里，你几乎就在解决方案中！
因此，让我们从更详细地写出要计算的内容开始。我们想知道一个列表是否曲折（即在某个点减少，在另一个点增加）。哪些列表符合此标准？好吧，如果出现以下情况，则列表曲折：
可以或多或少地直接将上述语句转换为 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？好吧，如果序列的长度大于一个，并且第一个元素大于第二个元素，或者它的尾部减少，则序列会减少：
(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)))))
increases并且decreases现在都可以非常简单地定义：
(define decreases (ever <))
(define increases (ever >))
没有更多要实现的功能 - 我们完成了。这个版本相对于 C 版本的优势是显而易见的——更容易推断这个程序会做正确的事情。这个程序的大部分内容都非常简单，所有的复杂性都被推到了ever函数中，这是一个非常通用的操作，在许多其他情况下都很有用。我确信通过搜索可以找到一个标准的（因此更值得信赖的）实现，而不是这个自定义的实现。
尽管有所改进，但该程序仍然不完美。有很多自定义递归，起初并不明显所有这些都是尾递归（尽管它是）。此外，该程序以多个条件分支和退出点的形式保留了 C 的微弱回声。借助惰性求值，我们可以获得更清晰的实现，为此我们将切换语言。
让我们回到问题定义。它实际上可以比第二部分更简单地说明 - “如果序列包含在两个方向上的相邻元素之间的比较，则它是曲折的（即未排序的）”。我可以或多或少地直接将那句话翻译成 Haskell 的一行：
zigzag xs = LT `elem` comparisons && GT `elem` comparisons
现在我需要一种方法来导出comparisons的每个成员xs与其后继者的比较列表。这并不难做到，也许最好用例子来解释。
> 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，它会很快返回，只要它发现第一个方向变化。
阅读代码的许多困难来自于遵循控制流的多个分支。许多这些分支确实是在努力避免计算超出我们的需要。但是通过惰性评估可以实现很多相同的事情，使程序更短，更真实地解决原始问题。
试试这个
(define sorted?
(lambda (l)
(cond ((null? l) #t)
(else (check-asc? (car l) (sorted? (cdr l))
(check-desc? (car l) (sorted? (cdr l))))))
(define check-asc?
(lambda (elt lst)
(cond ((null? lst) #t)
(else (or (< elt (car lst)) (= elt (car lst))) (check-asc? (car lst) (cdr lst))))))
(define check-desc?
(lambda (elt lst)
(cond ((null? lst) #t)
(else (or (< elt (car lst)) (= elt (car lst))) (check-desc? (car lst) (cdr lst))))))
我自己是新手。我没有测试过这段代码。仍在为递归而苦苦挣扎。请告诉我它是否有效或它给出了什么错误。
我之前给出的答案真的很糟糕。
我在 DrScheme 中运行了代码，它给出了错误。
不过我已经修改过了。这是一个有效的代码：
(define sorted?
(lambda (l)
(cond ((null? l) #t)
(else (if (check-asc? (car l) (cdr l)) #t
(check-desc? (car l) (cdr l)))))))
(define check-asc?
(lambda (elt lst)
(cond ((null? lst) #t)
(else (if (or (< elt (car lst)) (= elt (car lst))) (check-asc? (car lst) (cdr lst))
#f)))))
(define check-desc?
(lambda (elt lst)
(cond ((null? lst) #t)
(else (if (or (> elt (car lst)) (= elt (car lst))) (check-desc? (car lst) (cdr lst))
#f)))))
检查案例：
（排序？'（5 4 3 2 1））返回#t
（排序？'（1 2 3 4 5））返回#t
（排序？'（1 2 3 5 4））返回#f
（排序？'（））返回#t
（排序？'（1））返回#t