自定义地图功能 - 它是如何工作的? [英] Custom map function - how does it work?

问题描述

对于不清楚的主题标题，我深表歉意.

我在 Scheme 中有这个函数，它是 map 函数的自定义实现.它工作正常，但我在试图理解它时迷路了.

I have this function in Scheme which is a custom implementation of the map function. It works fine, but I got lost trying to understand it.

(define (my-map proc . ls)
  (letrec ((iter (lambda (proc ls0)
                   (if (null? ls0)
                       '()
                       (cons (proc (car ls0)) 
                             (iter proc (cdr ls0))))))
           (map-rec (lambda (proc ls0)
                     (if (memq '() ls0)
                         '()
                         (cons (apply proc (iter car ls0)) 
                               (map-rec proc (iter cdr ls0)))))))
    (map-rec proc ls)))

问题在于cons (proc (car ls0)).如果我是正确的，当将 (1 2 3) (4 5 6) 传递给 ls 参数时，它的实际值将是 ((1 23) (4 5 6)).因此map-rec中的iter car ls0会将(1 2 3)传递给iter.因此，iter 中的 proc (car ls0) 将具有以下形式:(car (car (1 2 3)))，但这是不可能的，对吗?

The problem lays in cons (proc (car ls0)). If I'm correct, when passing (1 2 3) (4 5 6) to the ls parameter the actual value of it will be ((1 2 3) (4 5 6)). Therefore iter car ls0 in map-rec will pass (1 2 3) to iter. Hence proc (car ls0) in iter will have the form: (car (car (1 2 3))), but this is impossible, right?

我知道我的想法在某处有缺陷，但我不知道在哪里.

I know my thinking is flawed somewhere, but I can't figure out where.

推荐答案

以下是理解程序的一种方式:

Here's one way to understand the procedure:

• iter 助手与 map 相同，但操作的是单个列表.
• map-rec 帮助器概括了 iter，为列表列表工作，当至少一个列表为空时停止
• 这部分:(apply proc (iter car ls0)) 对每个列表的第一个元素应用程序；对 iter 的调用创建了列表中 car 部分的列表
• 这部分:(map-rec proc (iter cdr ls0)) 同时推进所有列表的递归；对 iter 的调用创建了列表中 cdr 部分的列表

• The iter helper is the same as map, but operating on a single list.
• The map-rec helper generalizes iter, working for a list of lists, stopping when at least one of the lists is empty
• This part: (apply proc (iter car ls0)) applies the procedure on the first element of each list; the call to iter creates a list of the car part of the lists
• And this part: (map-rec proc (iter cdr ls0)) simultaneously advances the recursion over all the lists; the call to iter creates a list of the cdr part of the lists

也许重命名程序会使事情变得更清楚.这是一个完全等效的实现，明确了 map-one 对单个列表进行操作而 map-many 对列表列表进行操作的事实:

Perhaps renaming the procedures will make things clear. Here's a completely equivalent implementation, making explicit the fact that map-one operates on a single list and map-many operates on a list of lists:

(define (map-one proc lst)  ; previously known as `iter`
  (if (null? lst)
      '()
      (cons (proc (car lst))
            (map-one proc (cdr lst)))))

(define (map-many proc lst) ; previously known as `map-rec`
  (if (memq '() lst)
      '()
      (cons (apply proc (map-one car lst))
            (map-many proc (map-one cdr lst)))))

(define (my-map proc . lst) ; variadic version of `map-many`
  (map-many proc lst))

它就像原来的my-map:

(my-map + '(1 2 3) '(4 5 6) '(7 8 9))
=> '(12 15 18)

并且您可以检查 map-one 是否真的是一个适用于单个列表的 map:

And you can check that map-one is really a map that works on a single list:

(map-one (lambda (x) (* x x))
         '(1 2 3 4 5))
=> '(1 4 9 16 25)

查看(map-one car lst)对列表的效果:

(map-one car '((1 4 5) (2 6 7) (3 8 9)))
=> '(1 2 3)

同样，看看 (map-one cdr lst) 是如何工作的:

Likewise, see how (map-one cdr lst) works:

(map-one cdr '((1 4 5) (2 6 7) (3 8 9)))
=> '((4 5) (6 7) (8 9))

这篇关于自定义地图功能 - 它是如何工作的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！