Notes: Imperative to Functional, Part 5

Let's look something easier! How to add 1 to each list element?

def addOne(list):
    result = []
    for ele in list:
        result.append(ele + 1)
    return result

What if it's written functionally?

def addOne(list):
    return [] if list == [] else [list[0] + 1] + addOne(list[1:])

What if you want all list elements multiplied by 3?

def multiplyThree(list):
    return [] if list == [] else [list[0] * 1] + multiplyThree(list[1:])

How can all list elements be 'xxx'? Why not simply write a general map:

def map(func, list):
    return [] if list == [] else [func(list[0])] + map(func, list[1:])

Then, if you want to add 1 to each list element, you can do as such:

map(lambda ele: ele + 1, list)

Multiplying all list elements by 3 is as follows:

map(lambda ele: ele * 3, list)

If you want to 'xxx' all list elements, just...

map(lambda ele: xxx(ele), list)

Similarly, How to filter out list elements greater than 3?

def greatThanThree(list):
    result = []
    for ele in list:
        if ele > 3:
            result.append(ele)
    return result

Rewrite it functionally?

def greatThanThree(list):
    return [] if list == [] else \
        ([list[0]] + greatThanThree(list[1:]) if list[0] > 3 else greatThanThree(list[1:]))

What if you want filter list elements less than 3? You will write something similar to the above structure, so just define a filter directly!

def filter(func, list):
    return [] if list == [] else \
        ([list[0]] + filter(func, list[1:]) if func(list[0]) else filter(func, list[1:]))

Then, to filter list elements less than 3 is as follows:

filter(lambda ele: ele > 3, list)

Here you can see, map and filter are very common operations, just as fold mentioned in previous articles. Have you found that, however? The structure of map or filter is similar to fold? Actually, you can also implement map and filter with fold. For example, you can use Python's reduce, an implementation of foldLeft, to define a map:

def map(func, list):
    return reduce(lambda lt, elem: lt + [func(elem)], list, [])

You can also use reduce to implement filter:

def filter(func, list):
    return reduce(lambda lt, elem: lt + [elem] if func(elem) else lt, list, [])

Using reduce to add 1 to all list elements is ok but it'll be reduce(lambda lt, elem: lt + [elem + 1], list, []). Directly reduce the entire list to filter list elements less than 3 is no problem, but you'll write reduce(lambda lt, elem: lt + [elem] if elem> else lt, list, []). At this time, it's better to write more clear code such as map(lambda ele: ele + 1, list) and filter(lambda ele: ele> 3, list) respectively. Of course, addOne(list) and greaterThanThree(list) are more clear. That's the problem of readability. That's why we said that don't go too far while using general reduce, map and filter. If you want, you can write almost everything with map, filter and reduce. But if you can get readability with a little encapsulation, why not do it? Which is better to sum up [1, 2, 3]? Writing sum([1, 2, 3]) with Python's built-in sum or reduce(lambda s, e: s + e [1, 2, 3], 0) or reduce(int.__add__, [1, 2, 3], 0)?

In addition to reduce, there are also map and filter in Python's functools, but their return value are different from map and reduce defined above. Python's map and filter don't directly return a list, they return map and filter object respectively. Simply speaking, these two objects are generators. If you want to get a list, you can use list. For example, list(map(int.__add__, [1, 2, 3])) or list(filter(lambda ele,: ele,> 3, [1, 2, 3, 4, 5])).

In fact, some languages have list comprehensions. It makes you to do map and filter in a relatively simple syntax. In Python, for example, you can add 1 to all list elements with [ele + 1 for ele in list]. To filter list elements greater than 3, you can use [ele for ele, in list if ele > 3]. You guys familiar with Python should know this syntax.

Basically, problems that can be solved by map and filter can be also cleared up with list comprehensions. But something done by list comprehensions would be achieved troublesomely by map and filter. For example, a nested list comprehension is such a situation:

[(i, j) for i in [1, 2, 3] for j in [4, 5, 6]]

This will produce [(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5) , (3, 6)]. If you implement it with Python's reduce and map defined above, you would have to write down:

reduce(list.__add__, map(lambda i: map(lambda j: (i, j),  [4, 5, 6]), [1, 2, 3]))

A list comprehension is not just a more clear syntax, however. In some languages, it will look more like a mathematical expression. For example, a comprehension for a set that contains the positive even integers from 1 to 100 is {2 * x | x ∈ {1, 2..100}}. If you use Haskell's list comprehension, it will be [2 * x | x <- [1, 2 .. 100]], looks really like the original mathematical definition.