How the map function implemeted in racket

10,827

How to implement map

The map function walks a list (or multiple lists), and applies a given function to every value of a list. For example mappiing add1 to a list results in:

> (map add1 '(1 2 3 4))
'(2 3 4 5)

As such, you can implement map as a recursive function:

(define (map func lst)
  (if (empty? lst)
    '()
    (cons (func (first lst)) (map func (rest lst)))))

Of course, map can accept any number of arguments, with each element passed to the given prop. For example, you can zip two lists together using map list:

> (map list '(1 2 3) '(a b c))
'((1 a) (2 b) (3 c))

To implement this variable arity map, we need to make use of the apply function:

(define (map proc lst . lst*)
  (if (empty? lst)
      '()
      (cons (apply proc (first lst) (map first lst*))
            (apply map proc (rest lst) (map rest lst*)))))

Now, this does assume all of the given lists have the same length, otherwise you will get some unexpected behavior. To do that right you would want to run empty? on all lists, not just the first one. But...when you use it, you get:

> (map list '(a b c) '(1 2 3))
'((a 1) (b 2) (c 3))

Note that map here calls itself recursively 3 times. A faster implementation might do some unrolling to run faster. A better implementation would also do proper error checking, which I have elided for this example.

How Racket's map is implemented

If you open up DrRacket (using the latest Racket 7 nightly) and make the following file:

#lang racket

map

You can now right click on map and select Open Defining File. From here, you can see that map is renamed from the definition map2. The definition of which is:

(define map2
   (let ([map
          (case-lambda
           [(f l)
            (if (or-unsafe (and (procedure? f)
                                (procedure-arity-includes? f 1)
                                (list? l)))
                (let loop ([l l])
                  (cond
                   [(null? l) null]
                   [else
                    (let ([r (cdr l)]) ; so `l` is not necessarily retained during `f`
                      (cons (f (car l)) (loop r)))]))
                (gen-map f (list l)))]
           [(f l1 l2)
            (if (or-unsafe
                 (and (procedure? f)
                      (procedure-arity-includes? f 2)
                      (list? l1)
                      (list? l2)
                      (= (length l1) (length l2))))
                (let loop ([l1 l1] [l2 l2])
                  (cond
                   [(null? l1) null]
                   [else 
                    (let ([r1 (cdr l1)]
                          [r2 (cdr l2)])
                      (cons (f (car l1) (car l2)) 
                            (loop r1 r2)))]))
                (gen-map f (list l1 l2)))]
           [(f l . args) (gen-map f (cons l args))])])
     map))
Share:
10,827
Alexander Gorelik
Author by

Alexander Gorelik

Multi Developer.

Updated on June 14, 2022

Comments

  • Alexander Gorelik
    Alexander Gorelik over 1 year

    How does the map function implemented in racket and why, recursion or iteration.

    Maybe some implementation example

    • uselpa
      uselpa over 5 years
      Just look at the source code... (map.rkt, in Dr.Racket right click, "open defining file")
  • Alexander Gorelik
    Alexander Gorelik over 5 years
    Thanks for the details but my question was how map implemented in racket and not how to implement map by myself.
  • Leif Andersen
    Leif Andersen over 5 years
    Fair point. I've updated the answer to also include the Racket7 map implementation.