I am creating an evaluator for scheme in scheme, and one of the features I want it to have is map. However, all the definitions for map I've found do not allow for multiple lists.
For example:
(define (my-map proc lis)
(cond ((null? lis)
'())
((pair? lis)
(cons (proc (car lis))
(my-map proc (cdr lis))))))
This definition of map is 'incomplete' because, for example, you cannot add 2 lists of numbers with it like so (it only allows one list as an argument):
(my-map + '(1 2 3) '(4 5 6))
How do I modify the above map definition to allow an arbitrary number of lists?
You can define a multi-map procedure that works with multiple lists in terms of a one-map procedure that works for just one list (that's what your my-map procedure is doing, although the second condition is a bit unusual).
Here's how, assuming that all the lists have the same length and that at least one list is passed as parameter to multi-map:
(define (one-map proc lst)
(if (null? lst)
'()
(cons (proc (car lst))
(one-map proc (cdr lst)))))
(define (multi-map proc . lst)
(if (null? (car lst))
'()
(cons (apply proc (one-map car lst))
(apply multi-map proc (one-map cdr lst)))))
For example:
(multi-map + '(1 2 3) '(4 5 6) '(7 8 9))
=> '(12 15 18)
Well, the syntax for allowing my-map to take multiple lists is simply (define (my-map mapper lst1 . lsts) ...).
But that's not what you're really asking, is it? The general implementation approach is as follows:
- See if any list is empty. If so, return empty list.
- Collect the first element of each list, and pass them as arguments to call the mapper with.
- Cons the result of that mapper call with a recursive call to
my-map, using the rest of each list.
Steps 2 and 3 will likely be implemented using the one-list version of map.
map is a library procedure. Eg. You don't need to implement it in your evaluator as a primitive if you implement define. It is however defined in the SRFI-1 List library and it comes with a reference implementation and depending on what your evaluator has (continuations, multiple values, macroes) you may need to edit it a little or implement said constricts to make it work. The code that does map:
(define (map-in-order f lis1 . lists)
(check-arg procedure? f map-in-order)
(if (pair? lists)
(let recur ((lists (cons lis1 lists)))
(receive (cars cdrs) (%cars+cdrs lists)
(if (pair? cars)
(let ((x (apply f cars))) ; Do head first,
(cons x (recur cdrs))) ; then tail.
'())))
;; Fast path.
(let recur ((lis lis1))
(if (null-list? lis) lis
(let ((tail (cdr lis))
(x (f (car lis)))) ; Do head first,
(cons x (recur tail))))))) ; then tail.
