Evaluating Function in Lisp

Question

I'm new to Lisp and need help understanding this function and the evaluation of (map length '((a b c) (1 2 3 4 5) (v1 v2 v3 v4 v5 v6))))

The value is (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

In general, the idea of mapping is that for any list (define lst (list a b c d ... )) and function f, the value of (map f lst) is the same as the value of (list (f a) (f b) (f c) (f d) ...).

---

Let's simulate evaluation as a series of reduction steps:

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

...

As for your second example, '((a b c) (1 2 3 4 5) (v1 v2 v3 v4 v5 v6)) is the same as (list '(a b c) '(1 2 3 4 5) '(v1 v2 v3 v4 v5 v6)), i.e. it is a list with three elements in it; so the reduction becomes

(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.