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