Content deleted Content added
m Reverted 1 edit by Raymond Swindon identified as test/vandalism using STiki |
→Optimizations: Fixed grammar. Tags: Mobile edit Mobile web edit |
||
Line 53:
Map functions can be 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>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.
<source lang="haskell">
| |||