Content deleted Content added
Line 20:
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>.
The implementation of map above on singly-linked lists is not [[tail recursion|tail-recursive]], so 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.
rev_map f l = foldl (\ys x -> f x : ys) [] l
Since reversing a singly-linked list is also tail-recursive, reverse and reverse-map can be composed to perform normal map in a tail-recursive way.
==Haskell's Functor class==
| |||