高阶函数

Question

给定，

(define (reduce f id lis)
    (if (null? lis) id
      (f (car lis) (reduce f id (cdr lis)))))

列表的长度可以用 reduce 来定义（相对于 从头开始使用递归定义）as

(define (mylength lis) (reduce  (lambda (x n) (+ 1 n)) 0 lis)).

定义列表函数mymap（类似于map），它接受一个一元函数uf和一个列表lis在reduce方面，即通过确定

中对应的f和id

(mymap uf lis) = (reduce f id lis),

回想一下 mymap returns 对输入列表中的每个元素调用该函数所产生的列表，例如 (mymap (lambda(x) (* 2 x)) '(1 2 3)) = (2 4 6).

稍微解释一下这是如何完成的会有所帮助，而不是一个公然的回答。谢谢。

Answer 1

我们有

(mymap uf lis) = (reduce f id lis) = 
 = (if (null? lis) id
     (f (car lis) (reduce f id (cdr lis))))

必须等于

 = (if null? lis) '()
     (cons (uf (car lis)) (mymap uf (cdr lis))))

匹配对应的实体，得到

id == '()

而且，由于(mymap uf lis) = (reduce f id lis)，它也是(mymap uf (cdr lis)) = (reduce f id (cdr lis))，所以我们有

(f x y) = (cons (uf x) y)

因此，我们定义

(define (mymap uf xs)   ; multiple `x`-es :)
  (reduce (lambda (x r)
             (cons .... r))
          '()
          xs ))

你的 reduce 是一个 right fold：它的组合函数接收参数列表 xs 的一个元素 x，以及处理其余元素的递归结果列表，如 r。

r 具有 xs 其余部分的所有元素，这些元素已通过 uf 映射。要将给定元素 x 与此递归结果 r 组合，剩下要做的就是将 cons 和 (uf x) 合并到 r 上。

现在通过编写实际代码来代替那里的点 .... 来完成定义应该没有问题。