# Map

`map`

is an *enzyme* - it transforms a list (a structure) into a list of same length using `cons`

(which it captures by being a closure).

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

homogeneous lists

fun map (f, xs) = case xs of [] => [] | x::xs' => (f x) :: (map(f, xs'))

constant-space O(2n) - conses two lists, requires O(n) reverse

(define (map f xs) (define (map3 f xs ys) (if (null? xs) (reverse ys) (map3 f (cdr xs) (cons (f (car xs)) ys)))) (map3 f xs '()))

In terms of foldr `map f = foldr (Cons . f ) Nil`

(define map (lambda (f xs) (foldr (lambda (x xs) (cons (f x) xs)) '() xs)))

Haskell (omitting type signature clutter)

map _ [] = [] map f (x:xs) = f x : map f xs

or just

map f = foldr ((:) . f) []

tail-recursive, O(2n) - the cost of `reverse`

map f = reverse . foldl (flip ((:) . f)) []

non-tail-recursive

map(F, [H|T]) -> [F(H)|map(F, T)]; map(F, []) when is_function(F, 1) -> [].

list comprehensions

map(F, L) -> [F(X) || X <- L].

Shen, using the tail-recursive helper procedure - same as foldl + reverse - O(2n) - reverse is O(n).

(define map F X -> (map-h F X [])) (define map-h _ [] X -> (reverse X) F [X | Y] Z -> (map-h F Y [(F X) | Z]))

produces a closure over given `cons`

and `f`

mapFB c f = \x ys -> c (f x) ys

to be used with `foldr`

map f = foldr (mapFB (:) f) []

*in-place* definition

map f = foldr ((:) . f) []

which could be rewritten as `foldl`

of `flip`

`cons`

+ `reverse`

;; map id = id (check-expect ((partially map id) '(2 1)) '(2 1)) ;; map (f . g) = map f . map g (check-expect ((partially map (compose square (lambda (x) (* 2 x)))) '(2 1)) ((compose (partially map square) (partially map (lambda (x) (* 2 x)))) '(2 1))) ;; f . head = head . map f (check-expect ((compose square car) '(2 1)) ((compose car (partially map square)) '(2 1))) ;; map f . tail = tail . map f (check-expect ((compose (partially map square) cdr) '(2 1)) ((compose cdr (partially map square)) '(2 1))) ;; map f . reverse = reverse . map f (check-expect ((compose (partially map square) reverse) '(2 1)) ((compose reverse (partially map square)) '(2 1))) ;; map f . concat = concat . map (map f) (check-expect ((compose (partially map square) concat) '((2) (1))) ((compose concat (partially map (partially map square))) '((2) (1))))

**Note:**See TracWiki for help on using the wiki.