In the recipe, we have implemented map in two ways. Both implementations are described here as follows:
- The map function is defined as map f (x:xs) = f x : map f xs. Here, the mapping function f is applied to the first element, and then we will recurse using the remaining list and then join the result. Suppose the input list is [1,2,3,4,5], and we apply f to it. Then, our map will work in the following way. (Note that the function f is categorically not defined concretely to simplify the explanation of map.) As you can see, the result list keeps expanding towards the right (for example, f 1 : <rest of the list expanded here>):
map f [1,2,3,4,5] = f 1 : map f [2,3,4,5]
= f 1 : (f 2 : map f [3,4,5])
= f 1 : (f 2 : (f 3 : map f [4,5]))
= f 1 : (f 2 : (f 3 : (f 4 : map f [5])))
= f 1 : (f 2 : (f 3 : (f 4 : (f 5 : map f []))))
= f 1 : (f 2 : (f 3 : (f 4 : (f 5 : []))))
-- reducing further
= f 1 : f 2 : f 3 : f 4 : f 5 : []
- The tail recursive function map' is defined using the worker pattern. Instead of building a stack during recursion such as implemented in preceding section, it builds the argument. The worker function map1 that is used by map' is shown here:
map' f [1,2,3,4,5] = map1 [1,2,3,4,5] []
= map1 [2,3,4,5] [f 1]
= map1 [3,4,5] [f 2, f 1]
= map1 [4,5] [f 3, f 2, f 1]
= map1 [5] [f 4, f 3, f 2, f 1]
= map1 [] [f 5, f 4, f 3, f 2, f 1]
-- When input is empty, the result is reversed and
returned
= [f 1, f 2, f 3, f 4, f 5]
- In the tail-recursive version, the list builds up, but in the reversed order. Hence, when we return the final value, we have to reverse the list.