地图功能在racket中是如何实现的

Question

Racket中的map函数是如何实现的以及为什么，递归还是迭代。

也许一些实现示例

Answer 1

如何实现地图

该map函数遍历一个列表（或多个列表），并将给定函数应用于列表的每个值。例如，映射add1到列表会导致：

> (map add1 '(1 2 3 4))
'(2 3 4 5)

因此，您可以实现map为递归函数：

(define (map func lst)
  (if (empty? lst)
    '()
    (cons (func (first lst)) (map func (rest lst)))))

当然，map可以接受任意数量的参数，每个元素都传递给给定的 prop。例如，您可以使用以下命令将两个列表压缩在一起map list：

> (map list '(1 2 3) '(a b c))
'((1 a) (2 b) (3 c))

为了实现这个可变数量映射，我们需要使用以下apply函数：

(define (map proc lst . lst*)
  (if (empty? lst)
      '()
      (cons (apply proc (first lst) (map first lst*))
            (apply map proc (rest lst) (map rest lst*)))))

现在，这确实假设所有给定的列表都具有相同的长度，否则您将得到一些意外的行为。为了正确地做到这一点，您需要empty?在所有列表上运行，而不仅仅是第一个列表。但是......当你使用它时，你会得到：

> (map list '(a b c) '(1 2 3))
'((a 1) (b 2) (c 3))

注意map这里递归调用了3次。更快的实现可能会进行一些展开以加快运行速度。更好的实现还可以进行适当的错误检查，我在本示例中省略了该检查。

Racket的地图是如何实现的

如果您打开 DrRacket（使用最新的 Racket 7 nightly）并创建以下文件：

#lang racket

map

您现在可以右键单击map并选择Open Defining File。从这里，您可以看到它map是根据定义重命名的map2。其定义为：

(define map2
   (let ([map
          (case-lambda
           [(f l)
            (if (or-unsafe (and (procedure? f)
                                (procedure-arity-includes? f 1)
                                (list? l)))
                (let loop ([l l])
                  (cond
                   [(null? l) null]
                   [else
                    (let ([r (cdr l)]) ; so `l` is not necessarily retained during `f`
                      (cons (f (car l)) (loop r)))]))
                (gen-map f (list l)))]
           [(f l1 l2)
            (if (or-unsafe
                 (and (procedure? f)
                      (procedure-arity-includes? f 2)
                      (list? l1)
                      (list? l2)
                      (= (length l1) (length l2))))
                (let loop ([l1 l1] [l2 l2])
                  (cond
                   [(null? l1) null]
                   [else 
                    (let ([r1 (cdr l1)]
                          [r2 (cdr l2)])
                      (cons (f (car l1) (car l2)) 
                            (loop r1 r2)))]))
                (gen-map f (list l1 l2)))]
           [(f l . args) (gen-map f (cons l args))])])
     map))