Notes: Imperative to Functional, Part 3

The key point of functional programming is to decompose problems. An example to calculate the length of a list imperatively is as follows:

def length(list):
    c = 0
    for i in list:
        c += 1
    return c

It's a common example to rewrite it functionally in articles talking about functional programming:

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

You can pass a list to length. The concept here is very simple. If it's an empty list, length returns 0. If a list is not empty, length will plus 1 and the length of the tail list. This processing will continue until an empty list is reached. Similarly, how to sum up a list of integers? If it's written imperatively, it can be defined as follows:

def sum(list):
    acct = list[0]
    for i in range(1, len(list)):
        acct += list[i]
    return acct

As 'Notes: From Imperative to functional (2)' mentioned, if you are using loops to process list elements sequentially, you can basically solve them by a recursive solution. You don't need counters. The previous length is an example, while the above sum can be changed as follows:

def sum(list):
    def rsum(lt, at):
        return at if lt == [] else rsum(lt[1:], at + lt[0])
    return rsum(list, 0)

Here, rsum feels like length. If you rewrite length as follows:

def length(list):
    def rlen(lt, at):
        return at if lt == [] else rlen(lt[1:], at + 1)
    return rlen(list, 0)

Now, rsum and rlen has exactly the same structure. The differences are function names and ways to deal with the second argument before rsum and rlen are called again. Why don't you write a generic foldLeft?

def foldLeft(lt, func, at):
    return at if lt == [] else foldLeft(lt[1:], func, func(at, lt[0]))

Then length can be written as:

def length(list):
    return foldLeft([1, 2, 3], lambda at, elem: at + 1, 0)

And sum can be written as:

def sum(list):
    return foldLeft([1, 2, 3], lambda at, elem: at + elem, 0)

foldLeft is a really versatile function that can be used in millions of different ways. In Python, there's a functools.reduce function, it's a function implemented in foldLeft concepts. We've seen an example in 'Notes: From Imperative to functional (1)'. If you want to calculate a value from a list by an iterative loop, you can try foldLeft. But sometimes, the scenario is not as simple as sum or length. As 'Notes: From Imperative to Functional (1)' mentioned, to change imperative code into functional style, you need cleaner code and sensitivity of control flows, such as:

def eval(expr):
    stack = []
    for c in toPostfix(expr):
        if c in "+-*/":
            p2 = stack.pop()
            p1 = stack.pop()
            stack.append({'+': float.__add__,
                          '-': float.__sub__,
                          '*': float.__mul__,
                          '/': float.__floordiv__}[c](p1, p2))
        else:
            stack.append(float(c))
            
    return stack[-1]

eval is implemented imperatively. Can you figure out where foldLeft can be applied? They are in for c in toPostfix(expr) and return stack[-1]. Simply speaking, iterates expr, and then takes the latest value of stack. If you've a beginner of functional programming, I believe it's difficult to tell it out. I recommend you to start from simple examples, such as length and sum. These examples have simple control flows. After enough exercises, you'll have feeling with complex flows.

So, how to modify the above eval by foldLeft? The beginning stack has told you. The initial state of stack is empty. Huh? But, expr is not a list! The initial value should be an list element, isn't it? Or at least, its type should be the same as that of list elements. Who said that? Not true. The initial and return value of foldLeft can have different types from list elements. Here, the initial and return type would be list. The next step is to pull out the function passed in:

from functools import reduce
def eval(expr):
    def doStack(stack, c):
        if c in "+-*/":
            return stack[0:-2] + [
                {'+': float.__add__,
                 '-': float.__sub__,
                 '*': float.__mul__,
                 '/': float.__floordiv__}[c](stack[-2], stack[-1])]
        else:
            return stack + [float(c)]
    return reduce(doStack, toPostfix(expr), [])[-1]

The above example is modified directly by reduce, Python's foldLeft implementation. As mentioned previously, if you use an iterative loop to calculate a value, you can rewrite it with foldLeft. But it's not recommended that everything is solved by foldLeft. Actually, procExpr in 'Notes: From Imperative to functional (2)' could be implemented by foldLeft, but readability is not good. foldLeft is good to reuse control flows about getting a value from one iteration. But to some extent, it would have poor readability. Deliberate upon reusability and readability while considering foldLeft.

Of course, if there is foldLeft, there's also foldRight. You can implement it by yourself. foldLeft and foldRight are interchangeable if there's no consideration for associations. The other consideration is whether the type of lists is an algebraic data type. If you're concatenating two lists with + while calling foldLeft, and their type is an algebraic data type, you'll find performance issue while the right list of + is long. If you try foldRight and cons(:), it will have better performance. I'll talk about this afterward.