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