方案:高阶过程和递归

Question

我正在使用方案作为我正在学习的课程的一部分。我被告知要在作业中使用高阶函数。然而，这个指令似乎有点不清楚。

我不完全理解高阶过程的概念。我可以用递归来做所有的问题，但这是一样的。有没有人能用递归函数和用高阶过程编写的函数的例子来解释它？

作为第二个问题：

示例:尝试获取所有奇数

我可以使用(flatten (map odd ((1 4 5) (4 5 1 4 9))))，但如果有嵌套列表，我是否可以在嵌套列表上使用map：

(flatten (map odd ((1 3 (9 5 7))))；有没有这样做的函数或者干净利落的方法？

Answer 1

高阶函数的要点是减少代码中的样板，并减少循环(从技术上讲它是一个递归，但它的目的是循环，因此我将其称为循环)和实际逻辑之间的耦合。这里有一个例子(重新抓取所有的奇数)：一个手动循环看起来像这样：

(define (filter-odd lst)
  (cond ((null? lst) '())
        ((odd? (car lst)) (cons (car lst) (filter-odd (cdr lst))))
        (else (filter-odd (cdr lst)))))

但请注意，您已经在一个函数中实现了循环和过滤。这使得更难弄清楚函数在做什么，因为这两个不相关的操作耦合在一起。对于更高级别的函数，您可以执行不同的操作：

(define (filter pred lst)
  (cond ((null? lst) '())
        ((pred (car lst)) (cons (car lst) (filter pred (cdr lst))))
        (else (filter pred (cdr lst)))))

(define (filter-odd lst)
  (filter odd? lst))

现在请注意，odd?是如何从循环逻辑中分离出来的，循环逻辑现在已经分离为filter？filter现在接受一个函数对象，该对象决定是否保留该项，并且filter的调用者可以插入他们选择的任何函数。

这就是高阶函数的含义:它是一个以函数对象为参数的函数，用于定制其操作。

正如在问题的原始编辑中所提到的，map是另一个高阶函数，但它不是从列表中过滤项目，而是返回原始列表中每个项目的转换，其中特定的转换由map的调用者通过一个参数给出。

为了回答您关于展平等的实际问题，(map filter-odd '((1 3 (9 5 7))))将返回一个包含单个项的列表，即调用(filter-odd '(1 3 (9 5 7)))的结果。所以不，map不会为你递归子列表(filter也不会)。

但您可以先扁平化输入(因为无论如何都会扁平化输出)，然后直接对其调用filter-odd。我希望这会给你带来你所期望的结果。

(我将odd重命名为filter-odd，因为这不太可能与odd? (谓词)混淆。)

奖励材料

顺便说一下，filter和map都是一个更通用的高阶函数的特化，称为折叠(或者更具体地说，右折)。Folds可以表示filter或map都无法容纳的内容，但以某种方式涉及遍历列表中的所有项。下面是一个length函数的示例，表示为一个文件夹：

(define (foldl func init lst)
  (if (null? lst) init
      (foldl func (func (car lst) init) (cdr lst))))

(define (length lst)
  (foldl (lambda (elem count)
           (+ count 1))
         0 lst))

这里的好处是length函数不必担心遍历列表:这是由fold处理的。它只需要考虑在每次迭代中做什么(在这里，这只是简单地将1加到count上，从0开始)。

在这种情况下，无论我们从左侧还是右侧遍历，长度都是相同的，而在Scheme中，从左侧遍历更节省空间，因此我们更喜欢这样。但是对于实现map和filter，右折叠是必要的(否则元素会颠倒过来-尝试在下面的函数中用foldl替换foldr，你就会看到)：

(define (foldr func init lst)
  (if (null? lst) init
      (func (car lst) (foldr func init (cdr lst)))))

(define (map func lst)
  (foldr (lambda (elem result)
           (cons (func elem) result))
         '() lst))

(define (filter pred lst)
  (foldr (lambda (elem result)
           (if (pred elem)
               (cons elem result)
               result))
         '() lst))