Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Implementation of variadic map function in Scheme

As you can see in the example below, map function in Scheme is variadic function.

> (map (lambda (number1 number2)
     (+ number1 number2))
   '(1 2 3 4)
   '(10 100 1000 10000))
'(11 102 1003 10004)

I want to implement this variadic option, but I only succeeded to find the two arguments map implementation:

(define (map f lst)
   (if (null? lst)
       '()
       (cons (f (car lst)) (map f (cdr lst)))))

Can someone help me implement variadic map function?

like image 748
Nir Avatar asked Feb 07 '14 13:02

Nir


1 Answers

In Scheme, you can write a variadic function as (lambda x ...), in which case x gets bound to the entire list of arguments, or by using an improper lambda list, e.g., (lambda (a b c . ds) ...), which takes at least three arguments, and binds ds to the list of the remaining arguments. The code you're trying to write, then, would be something like (I'm writing in R5RS Scheme):

(define (my-map function list1 . more-lists)
  (define (some? function list)
    ;; returns #f if (function x) returns #t for 
    ;; some x in the list
    (and (pair? list)
         (or (function (car list))
             (some? function (cdr list)))))
  (define (map1 function list)
    ;; non-variadic map.  Returns a list whose elements are
    ;; the result of calling function with corresponding
    ;; elements of list
    (if (null? list)
        '()
        (cons (function (car list))
              (map1 function (cdr list)))))
  ;; Variadic map implementation terminates
  ;; when any of the argument lists is empty
  (let ((lists (cons list1 more-lists)))
    (if (some? null? lists)
        '()
        (cons (apply function (map1 car lists))
              (apply my-map function (map1 cdr lists))))))

This works as expected:

(my-map + '(0 2 5) '(1 2 3))
;=> (1 4 8)

Notice that to make this work, we needed a non-variadic map (here called map1) in order to do (map1 car lists) to get the argument list to call function with, and (map1 cdr lists) to get the rests of the lists to recurse with. To write a variadic map (here called my-map), you already need an implementation of the non-variadic map.

like image 101
Joshua Taylor Avatar answered Oct 03 '22 22:10

Joshua Taylor