我决定学习一些函数式语言，最终选择了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。
在函数式编程中，我应该如何思考？语法似乎很简单，但我不习惯这种逻辑。
具体实现
我会采用Ó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 >=)))))
letrec将sorted?定义为Óscar的内部帮助函数，并以两种方式调用它。
函数式思维
你选择了一个很好的例子来说明Scheme如何看待这个世界，而且你的实现已经有了很好的开端。(**here** more stuff '(1 2 3 4))放进去的东西，你都可以将其作为参数传递给另一个函数。也就是说，在函数式编程语言中，函数是一等公民。因此，你在比较中使用<=的事实意味着你可以将<=作为参数传递给另一个函数，该函数相应地进行比较。Óscar的答案很好地说明了这一点。(cond)块主要组成的函数。在许多函数式编程语言（如Haskell、ML、OCaml、F#、Mathematica）中，你会获得比在Scheme中默认更强的模式匹配能力。因此，在Scheme中使用(cond)，你必须描述如何测试所寻找的模式，但这通常是相当简单的（例如，在这个实现中的(or (empty? lst) (empty? (cdr lst)))）。letrec而不是普通的let的原因。cdr）上重复该操作的事情，你都可以用这种方式来完成。命令式的for或while循环在Scheme中并非不可能（虽然在纯函数式语言（如Haskell）中它们几乎是不可能的），在许多情况下它们都有些不恰当。但是Scheme的灵活性使你作为开发者能够做出这个决定，在某些情况下可以进行重要的性能或可维护性优化。
继续探索
我在这里回答的第一个sorted?的实现将根据列表中看到的内容决定要传递给sorted-cmp的比较运算符。当我发现一个列表可以以两个相等的数字开头'(1 1 2 3 4 5)时，我就放弃了这个想法。但是当我再考虑一下，肯定有一种方法可以跟踪你是否已经确定了方向，并且只需要一次调用sorted-cmp。你可以考虑接下来探索这个问题。你差一点就对了，看这里：
(define sorted?
(lambda (lst)
(cond ((or (empty? lst) (empty? (cdr lst)))
#t)
(else (and (<= (car lst) (cadr lst))
(sorted? (cdr lst)))))))
(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
正如你所看到的，函数式编程是指尽可能通用地定义过程并将它们组合起来解决问题。你可以将函数作为参数传递，这有助于实现通用函数。
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;
}
可以将上述语句直接或多或少地翻译成Scheme函数：
(define (zigzag xs)
(and (> (length xs) 2)
(or (and (initially-increasing xs) (decreases xs))
(and (initially-decreasing xs) (increases xs))
(zigzag (cdr xs)))))
(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 >))
ever函数中，它是一个非常通用的操作，在许多其他上下文中也会很有用。我相信通过搜索，人们可以找到一个标准（因此更可靠）的实现，而不是这个定制的实现。让我们回到问题定义。它可以比第二部分中更简单地陈述为：“如果序列包含相邻元素之间的比较，这些比较在两个方向上进行，则该序列会呈现锯齿状（即非排序）。我可以将这句话直接或多或少地翻译成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，它将很快返回，一旦发现方向改变。
阅读代码时的许多困难来自于跟踪多个控制流分支。而其中许多分支实际上是为了避免计算我们不需要的部分。但是使用惰性评估可以实现同样的效果，使程序更短且更符合原始问题。
试试这个
(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)))))
检查的案例：
(sorted? '(5 4 3 2 1)) 返回 #t
(sorted? '(1 2 3 4 5)) 返回 #t
(sorted? '(1 2 3 5 4)) 返回 #f
(sorted? '()) 返回 #t
(sorted? '(1)) 返回 #t
let的一个原因是你只能对给定符号进行一次define，而let可以暂时覆盖现有的define。在小程序中，您总是可以知道哪些符号已经有定义，并且可以证明使用define是安全的。在稍微大一点的程序中，最安全的方法通常是使用let（以及它的朋友let*和letrec）来创建适当范围的临时定义。 - sblom