Оценка функции в Лиспе

Question

Я новичок в Лиспе и нужно помочь понять эту функцию и оценку (map length '((a b c) (1 2 3 4 5) (v1 v2 v3 v4 v5 v6))))

Значение является (3 5 6)

(define (map f list)  
    ; applies function f to each element of list 
    (if (null? list) 
    () 
     (cons (f (car list)) 
      (map f (cdr list))))) 

(define map-test-1 
    (map square '(1 2 3 4 5))) 
(define map-test-2 
    (map length '((a b c) (1 2 3 4 5) (v1 v2 v3 v4 v5 v6)))) 

Answer 1

В общем, идея отображения является то, что для любого список (define lst (list a b c d ...)) и функция f, значение (map f lst) совпадает с значением (list (f a) (f b) (f c) (f d) ...).

---

Давайте моделировать оценку в виде серии сокращения шагов:

(map square '(1 2 3 4 5) ) 
;; (map f  list   ) 
= (let ((f  square  )  ; definition 
      (list  '(1 2 3 4 5)))  ; of `map` 
     (if (null? list)    
     () 
      (cons (f  (car list)) 
       (map f (cdr list)))))  ; list is not `null?`, so 

= (let ((f  square  ) 
      (list  '(1 2 3 4 5))) 
     (cons (f  (car list))   ; car of list is 1 
       (map f (cdr list))))  ; cdr is '(2 3 4 5) 

= (cons (square 1) 
    (let ((f  square )  ; simulate the recursive call 
      (list  '(2 3 4 5)))  ; by updating the arguments 
     (map f list))) 

= (cons (square 1) 
    (let ((f  square ) 
      (list  '(2 3 4 5))) 
     (if (null? list) 
     () 
      (cons (f  (car list)) 
       (map f (cdr list)))))) 

= (cons (square 1) 
    (let ((f  square ) 
      (list  '(2 3 4 5))) 
     (cons (f  (car list)) 
       (map f (cdr list))))) 

= (cons (square 1) 
    (cons (square 2) 
     (let ((f  square ) 
       (list  '(3 4 5))) 
      (map f list)))) 

... 

Что касается второго примера, '((a b c) (1 2 3 4 5) (v1 v2 v3 v4 v5 v6)) такое же, как (list '(a b c) '(1 2 3 4 5) '(v1 v2 v3 v4 v5 v6)), т.е. это список с тремя элементами в нем; поэтому сокращение составляет

(let ((mylist (list '(a b c) '(1 2 3 4 5) '(v1 v2 v3 v4 v5 v6)))) 
    (let ((f  length  )  ; definition 
      (list  mylist  ))  ; of `map` 
     (if (null? list)    
     () 
      (cons (f  (car list)) 
       (map f (cdr list)))))) ; list is not `null?`, so 

= (let ((f  length  ) 
      (list  mylist  )) 
     (cons (f  (car list))   ; car of list is '(a b c) 
       (map f (cdr list))))  ; cdr is '((1 2 3 4 5) (v1 v2 v3 v4 v5 v6)) 

= (cons (length '(a b c)) 
    (let ((f  length  )  ; simulate the recursive call 
      (list  (cdr mylist))) ; by updating the arguments 
     (map f list))) 

= (cons (length '(a b c)) 
    (let ((f  length ) 
      (list  '((1 2 3 4 5) (v1 v2 v3 v4 v5 v6)))) 
     (if (null? list) 
     () 
      (cons (f  (car list)) 
       (map f (cdr list)))))) 

= (cons (length '(a b c)) 
    (let ((f  length ) 
      (list  '((1 2 3 4 5) (v1 v2 v3 v4 v5 v6)))) 
     (cons (f  (car list)) 
       (map f (cdr list))))) 

= (cons (length '(a b c)) 
    (cons (length '(1 2 3 4 5)) 
     (let ((f  length ) 
       (list  '((v1 v2 v3 v4 v5 v6)))) 
      (map f list)))) 

= (cons (length '(a b c)) 
    (cons (length '(1 2 3 4 5)) 
     (cons (length '(v1 v2 v3 v4 v5 v6)) 
     (let ((f  length) 
       (list  '())) 
      (if (null? list)    
      () 
      (cons (f  (car list)) 
        (map f (cdr list)))))))) ; list is now `null?`, so 

= (cons (length '(a b c)) 
    (cons (length '(1 2 3 4 5)) 
     (cons (length '(v1 v2 v3 v4 v5 v6)) 
     '()))) 

QED.