wiki:Functions/Map

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))))
Last modified 2 years ago Last modified on Nov 11, 2018, 7:26:44 AM
Note: See TracWiki for help on using the wiki.