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

{{{#!scheme
(define map (lambda (f xs)
                (if (null? xs)
                    '()
                    (cons (f (car xs)) (map f (cdr xs))))))
}}}
homogeneous lists
{{{#!sml
fun map (f, xs) =
  case xs of
       [] => []
     | x::xs' => (f x) :: (map(f, xs'))
}}}
constant-space O(2n) - conses two lists, requires O(n) [wiki:/Functions/Reverse reverse]
{{{#!scheme
(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 [wiki:Functions/Foldr foldr] {{{map f = foldr (Cons . f ) Nil}}}
{{{#!scheme
(define map (lambda (f xs)
                (foldr (lambda (x xs) (cons (f x) xs)) '() xs)))
}}}
Haskell (omitting type signature clutter)
{{{#!haskell
map _ []      =  []
map f (x:xs)  =  f x : map f xs
}}}
or just 
{{{#!haskell
map f = foldr ((:) . f) []
}}}
tail-recursive, O(2n) - the cost of {{{reverse}}}
{{{#!haskell
map f = reverse . foldl (flip ((:) . f)) []
}}}
non-tail-recursive
{{{#!erlang
map(F, [H|T])                     -> [F(H)|map(F, T)];
map(F, []) when is_function(F, 1) -> [].
}}}
list comprehensions
{{{#!erlang
map(F, L) -> [F(X) || X <- L].
}}}
Shen, using the tail-recursive helper procedure - same as [wiki:Functions/Foldl foldl] + [wiki:Functions/Reverse reverse] - O(2n) - [wiki:Functions/Reverse reverse] is O(n).
{{{#!lisp
(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}}}
{{{#!haskell
mapFB c f  =  \x ys -> c (f x) ys
}}}
to be used with {{{foldr}}}
{{{#!haskell
map f  =  foldr (mapFB (:) f) []
}}}
''in-place'' definition
{{{#!haskell
map f  =  foldr ((:) . f) []
}}}
which could be rewritten as {{{foldl}}} of {{{flip}}} {{{cons}}} + {{{reverse}}}
-----
{{{#!scheme
;; 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))))
}}}