Map (higher-order function): Difference between revisions

Revision as of 17:50, 11 March 2007

Revision as of 19:41, 11 March 2007

Line 17:

==Optimizations==

The mathematical basis of maps allow for a number of [[optimization]]s. If one has <code>map f . map g</code> ('.' is [[function composition]]) then it is the same as the simpler <code>map (f . g) xs</code>; that is,

<math>\left( \text{map}\,f \right) \circ \left( \text{map}\,g \right) = \text{map}\,\left( f \circ g \right)</math>. This particular optimization eliminates a possiblyan expensive second map by fusing it with the first map; thus it is a "map fusion"<ref>[http://www.randomhacks.net/articles/2007/02/10/map-fusion-and-haskell-performance "Map fusion: Making Haskell 225% faster"]</ref>.

Map functions can and often are defined in terms of a [[Fold (higher-order function)|fold]] such as <code>foldr</code>, which means one can do a "map-fold fusion": <code>f z . map g</code> is equivalent to <code>foldr (f . g) z</code>.