Notes: Imperative to Functional, Part 4

Before the end of 'Notes: From Imperative to functional (3)', I mentioned about foldRight. I just got a good example casually so it's time to talk about it.

Previous articles are using Python code for demonstration so I'll continue to use Python for demonstration. First, think about how to concatenate two lists in Python? Yes, + operator! Such as [1, 2, 3] + [4, 5, 6]. What if you want to insert an element before a list? You can't use 1 + [1, 2, 3]. We're considering an immutable data structure so we don't want to use the insert method of list. Let's think it again! What data structure should a list be?

In Python, there's something similar to an immutable list, a tuple! Let's use it to construct an immutable list. First, an empty immutable list is (). Then, an immutable list with elements is composed of a head element and a tail immutable list. So, an immutable list with an element 1 is (1, ()), an immutable list has the elements 1 and 2 is (1, (2, ())), the immutable list has the elements 1,2 and 3 is (1, (2, ( 3, ()))), and so on. According to this structure, if you want to put an element before an immutable list, you may define a cons function to do it.

def cons(elem, lt):
    return (elem, lt)

For convenience, let's define an lst function to create an immutable list:

def lst(*elems):
    return () if elems == () else cons(elems[0], lst(*elems[1:]))

Then, to construct an immutable list with elements 1, 2 and 3, just call lst(1, 2, 3) to get it. Get back to the problem just mentioned. We may use cons to put an element before an immutable list but how to concatenate two immutable lists? Python's tuple has a + operator to do this, but you can't use lst(1, 2, 3) + lst(4, 5, 6), because it will return (1 (2 (3 ())) , (5, (6, ()))), not the immutable list structure just defined above. The expected result should be (1, (2, (3, (4, (5, (6, ())))))). According to the definition of the immutable list structure, you must define a new concat function:

def concat(lt1, lt2):
    return lt2 if lt1 == () else cons(lt1[0], concat(lt1[1], lt2))

So concat(lst(1, 2, 3), lst(4, 5, 6)) will return (1, (2, (3, (4, (5, (6 ())))))). Well... (1, (2, (3, (4, (5, (6 ())))))) has poor readability so let's write a toStr function:

def toStr(lt):
    return '()' if lt == () else str(lt[0]) + ':' + toStr(lt[1])

Now, toStr(lst(1, 2, 3, 4, 5, 6)) will return '1:2:3:4:5:6:()'. The symbol ':' is used in functional languages conventionally. That's why we called putting an element before an immutable list is 'cons' but not 'prepend'. As your wish, you can also define a append function to append an element after an immutable list.

def append(l, elem):
    return concat(l, lst(elem))

So, what's the point? For the immutable list defined above, putting an element before an immutable list is easy. But if you want to concatenate two immutable lists, or append an element after an immutable list, you'll have to iterate all elements of the first list.

If you define a foldLeft function for an immutable list:

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

To convert lst(1, 2, 3) to lst('1 ', '2', '3 '), you'll have to:

foldLeft(lst(1, 2, 3), lambda at, digit: concat(at, lst(str(digit))), ())

Or:

foldLeft(lst(1, 2, 3), lambda at, digit: append(at, str(digit)), ())

However, append still calls concat. For this question, you'll have to visit all elements of at if you use foldLeft. If we define a foldRight function:

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

Then, converting lst(1, 2, 3) to lst('1 ', '2', '3 ') could be done as such:

foldRight(lst(1, 2, 3), lambda at, digit: cons(str(digit), at), ())

For this example, you don't have to visit all elements of at so the performance is better.

For problems which left-to-right visiting has no difference from right-to-left visiting, foldLeft or foldRight doesn't matter, such as foldRight(lst(1, 2, 3), int.__add__, 0) and foldLeft(list(1, 2, 3 ), int.__add__, 0) has no difference. But for the above mapping of lst(1, 2, 3) to lst('1 ', '2', '3 '), there will be performance differences.

In addition to considerations of foldLeft or foldRight, if a language supports the above data structure, you can take more thinking while concatenating two lists. Sometimes, you may try 'cons' instead. Let's take a look at a Scala example:

def eval(expr: String) = {
    ((Nil:List[Double]) /: toPostfix(expr)) {
        (stack, c) => {
            if("+-*/".contains(c)) {
                val op1 = stack.init.last
                val op2 = stack.last
                stack.init.init ++ List(c match {
                    case '+' => op1 + op2
                    case '-' => op1 - op2
                    case '*' => op1 * op2
                    case '/' => op1 / op2
                })
            } else stack ++ List(c.toString.toDouble)
        }
    }.last
}

Here, we use ++ to concatenate lists, it will visit the entire stack every time. If stack is long, it will have poor performance. The code can be changed to:

def eval(expr: String) = {
    ((Nil:List[Double]) /: Infix.toPostfix(expr)) {
        (stack, c) => {
            if("+-*/".contains(c)) {
                val op1 = stack.tail.head
                val op2 = stack.head
                (c match {
                    case '+' => op1 + op2
                    case '-' => op1 - op2
                    case '*' => op1 * op2
                    case '/' => op1 / op2
                }) :: stack.tail.tail
            } else c.toString.toDouble :: stack
        }
    }.head
}

The return value is the same, but this time without visiting the entire stack every time, the performance is better.