2

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?

pb22
  • 73
  • 2
  • 6

3 Answers3

4

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)
Óscar López
  • 232,561
  • 37
  • 312
  • 386
1

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:

  1. See if any list is empty. If so, return empty list.
  2. Collect the first element of each list, and pass them as arguments to call the mapper with.
  3. 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.

C. K. Young
  • 219,335
  • 46
  • 382
  • 435
  • would you really write this non-tail-recursive code in your *implementation*, and not some optimized [TRMC](http://stackoverflow.com/a/13256555/849891) stuff? I wonder why this point is almost never stressed as much as I think it should be. :) – Will Ness Jul 15 '13 at 16:34
1

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.
Sylwester
  • 47,942
  • 4
  • 47
  • 79