CODEWITHSUNDEEP
racket
Alexander Gorelik
Alexander Gorelik

Reputation: 4385

How the map function implemeted in racket

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

Maybe some implementation example

Upvotes: 4

Views: 18404

Answers (1)

Leif Andersen
Leif Andersen

Reputation: 22332

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

Upvotes: 9

Related Questions