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

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