scheme - 根据 reduce 定义 map

Question

我刚拿到 John Hughes 的论文 Why Functional Programming Matters ，我正在尝试使用 Scheme。

他定义的第一个高阶函数是reduce，我在Scheme中定义如下:

(define u-reduce
  (lambda (ff init lst)
    (if (null? lst)
      init
      (ff (car lst) (u-reduce ff init (cdr lst))))))

我可以使用这个函数在文章中重新创建一些 reduce 的应用程序，但是在从 reduce 到 map< 的过程中事情会分崩离析。

激励示例是 doubleall = reduce doubleandcons nil，其中 doubleandcons num list = cons (2*num) list。

我不确定如何将其转化为方案。我可以看到目标结果可以用:

(define doubleandcons
  (lambda (lst)
    (if (null? lst)
      '()
      (cons (* 2 (car lst)) (doubleandcons (cdr lst))))))

(doubleandcons '(1 2 3))
> (2 4 6)

但是看不到要传递给 reduce 的内容以使其将列表的每个元素加倍 - 也许是因为我一直跳转到 map 的版本(请参阅 u-map 下面)作为问题的解决方案。

我可以看到 init = '()，但看不到要将什么函数传递到 ff 位置来生成 u-reduce 表现得像 u-map。

(define u-map
  (lambda (ff lst)
    (if (null? lst)
      '()
      (cons (ff (car lst)) (u-map ff (cdr lst))))))

(u-map (lambda (x) (* 2 x)) '(1 2 3))
> (2 4 6)

这可能吗？或者也许我错过了重点？

Answer 1

Common Lisp reduce 是一个通用的fold。在 Scheme 中，您有 fold-right 按顺序处理元素。你的 u-reduce 就像一个正确的折叠一样，它的参数顺序相同。因此，以下内容应该适用于 R6RS/R7RS:

(define (my-map fun lst)
  (fold-right (lambda (x a) (cons (fun x) a)) '() lst))

如您所见，我在匿名函数中使用传递给 fold-right 的函数来执行 cons。

在其他版本的 Scheme 和 Racket 中，您可以通过使用 SRFI-1: List library 获得相同的行为。 , 许多实现都支持它，因此请查看它的文档，了解如何导入/需要它。