1

I apologize for the unclear topic title.

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)))

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.

4

1 回答 1

1

这是理解该过程的一种方法：

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

也许重命名程序会让事情变得清晰。这是一个完全等效的实现，明确了map-one对单个列表进行map-many操作并在列表列表上进行操作的事实：

(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适用于单个列表：

(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)工作：

(map-one cdr '((1 4 5) (2 6 7) (3 8 9)))
=> '((4 5) (6 7) (8 9))
于 2014-02-23T23:44:22.633 回答