Content deleted Content added
Use the license for your own material. Tags: Reverted Mobile edit Mobile web edit |
|||
Line 14:
square x = x * x
</syntaxhighlight>
Afterwards we may call
Line 89 ⟶ 90:
lead to the same result; that is, <math>\operatorname{map}(f) \circ \operatorname{map}(g) = \operatorname{map}(f \circ g)</math>. However, the second form is more efficient to compute than the first form, because each <code>map</code> requires rebuilding an entire list from scratch. Therefore, compilers will attempt to transform the first form into the second; this type of optimization is known as ''map fusion'' and is the [[functional programming|functional]] analog of [[loop 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 be and often
, 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>foldr f z . map g</code> is equivalent to <code>foldr (f . g) z</code>. The implementation of map above on singly linked lists is not [[tail recursion|tail-recursive]], so it may build up a lot of frames on the stack when called with a large list. Many languages alternately provide a "reverse map" function, which is equivalent to reversing a mapped list, but is tail-recursive. Here is an implementation which utilizes the [[fold (higher-order function)|fold]]-left function.
| |||