高阶函数和 Set 如何在 Scheme 上工作？

Question

usage: (twice square)
=> #<procedure>

usage: ((twice square) 2)
=> 16

usage: ((twice (twice square)) 10)
=> 10000000000000000

usage: (member 4 (list 1 2 4))  
=> #t

usage: (insert 4 (list 1 2))
=> (4 1 2)

我已经针对问题 2 尝试了以下代码（但它没有按照我想要的方式工作），而且我怎么不知道问题 1

(define (set? lst)      
  (cond ((null? lst) #t)
        ((member? (car lst) (cdr lst)) #f)
        (else (set? (cdr lst)))))

Answer 1

高阶函数是将函数作为参数（或 return 函数作为结果）的函数。您可以使用与普通函数相同的方式定义它们，使用 define。例如，map 将过程（在 Racket 中，函数称为过程）作为第一个参数，它在列表的每个元素上调用该过程：

> (map add1 '(1 2 3 4 5))
'(2 3 4 5 6)
> (map sub1 '(1 2 3 4 5))
'(0 1 2 3 4)

假设您想使用 map 将每个数字增加 2。您可以为此定义命名函数：

(define (add2 x) (+ x 2))

> (map add2 '(1 2 3 4 5))
'(3 4 5 6 7)

或使用lambda，创建匿名函数：

> (map (lambda (x) (+ x 2))
       '(1 2 3 4 5))
'(3 4 5 6 7)

这个函数不能从你程序的其他地方调用（除非你把它绑定到某个符号）并且在使用后被丢弃。

由 lambda 创建的函数也可以作为结果被 return 编辑。也许您经常需要添加一些数字并且不想每次都写 (lambda (x) ... ) 。所以，你可以这样写函数：

(define (adder y)
  (lambda (x) (+ x y)))

并与map一起使用：

> (map (adder 3) '(1 2 3 4 5))
'(4 5 6 7 8)
> (map (adder 4) '(1 2 3 4 5))
'(5 6 7 8 9)

注意创建的匿名函数会记住 y = 3 或 y = 4。实际上，Racket 中的所有函数都是词法闭包，它们会记住它们是在哪里创建的，以及那一刻绑定了哪些符号。

因此，您的解决方案将使用这些原则：

(define (square x)
  (* x x))

(define (twice f)
  (lambda (x) (f (f x))))

那么，((twice (twice square)) 10)可以改写为

> ((lambda (x) ((lambda (x) (square (square x)))
               ((lambda (x) (square (square x)))
               x))) 10)
10000000000000000

也就是 10^16。

> (= ((twice (twice square)) 10)
     (expt 10 16))
#t

我不确定您是否需要编写除 member 和 insert 之外的其他函数，因为在您的示例中，它们在列表中被调用并且没有 list->set 函数明确提及。

函数 member 必须重命名，如下所示：

(define (my-member v lst)
  (cond ((null? lst) #false)
        ((= v (car lst)) #true)
        (else (my-member v (cdr lst)))))

(内建函数member实际上是return的列表，但是这样就够了。)

使用 insert，您必须检查您的列表是否已经包含该元素，在这种情况下，return 按原样。

(define (insert v lst)
  (if (my-member v lst)
      lst
      (cons v lst)))

示例：

> (insert 3 '(1 2 3))
'(1 2 3)
> (insert 4 '(1 2))
'(4 1 2)

您可能还会发现 check-duplicates and remove-duplicates useful and there is already Racket library 用于处理集合。

How does higher order function and Set work on Scheme?