pascal-functional-learnings.md

This is my attempt at converting a solution to a pascal's triangle problem that I'd written in an imperitive manner into a functional one. I kind of hope that anyone reading this is also trying to figure out the meanings behind functional programming, I'm trying to describe all the steps that I go through.

It is a mini way of me trying to discover what being 'declarative' actually means.

I know the kind of definition e.g.:

1. "say what you want" not "how to do it"
2. picture vs recipie
3. sqrt(2) vs looping from x = 1 finding the mean of x and 2/x
4. SQL, Haskell vs C++, Java

This is what I understand about functional programming:

1. no side-effects
2. focus on the functions (functions are first class objects)

The imperative

Here was my imperative method to return the k-th row of Pascal's triangle. Now I'll be honest and say this took me hours to get a correct result when I first tried to implement it in an imperative manner.

class Solution:
    # @param A : integer
    # @return a list of integers
    def getRow(self, A):
        pascal = [1]

        for i in range(A):
            pascal.append(0)
            for j in range(i,0,-1):
                pascal[j] += pascal[j-1]

        return pascal

How do I say that declaratively?

It is supposed to be something like (see Functional Programming in Python):

for thing in collection:
    process(thing)

Although I don't really understand how that would be declarative. What's my collection?

I kind of understand how SQL is declarative

SELECT  field
FROM    table
WHERE   other_field > 5

Instead of doing one big for loop.

What I don't understand is how you can loop over an array looking at the current and previous elements.

To loop in a functional manner you need to be able to treat each element independently.

What I spotted was that you can copy and shift the array by one. So:

#             current row = [1,3,3,1]
#      append zero to row = [1,3,3,1,0] (1)
#     prepend zero to row = [0,1,3,3,1] (2)
# sum elements of 1 and 2 = [1,4,6,4,1]

This seems kind of neat, but I don't really know how inefficient this is.

I also don't know if that's very functional. But I'm pretty sure that you can then loop over the elements of the arrays and sum them in a list comprehension, which always seems to be 'functional' (it's final all encompassing functional solution suggested by this IBM article on Functional programming in Python).

The best I have so far is, for 'what' we want

for i in range(k) # k-th row
    current_row = get_next_row(current_row)

But I couldn't quite figure that out.

The next point that seems to be 'ok' with functional programming is recursion, which seems to be a sensible way of accessing current and next/previous

def get_next_row(row, i):
    if i = 0:
        return row
    return get_next_row(calc_new_row, i-1)

Haskell

At this point I turned to Stack Overflow. What I learned is that trying to search for functional programming solutions in Python isn't very rewarding. Most people write imperitively in Python so you get a lot of chaff in your search results.

What made more sense was searching for Haskell solutions. The second solution I came across was Making a list of lists to compute Pascal's triangle in Haskell, with this solution:

nextRow vs = [1] ++ zipWith (+) vs (tail vs) ++ [1]
allPascals = iterate nextRow [1]

Now you don't have to know a ton of Haskell to understand the code. Also it helps if you know the zip python syntax which is similar, for summing the elements of two arrays.

[x + y for x, y in zip(first, second)]

Also this is following my concept of summing one array and itself shifted (by taking the 'tail'):

# [1,3,3,1]
# [3,3,1]
# [4,6,4]

This gives you everything except the outer [1] elements, which get concatenated using the Haskell ++ operator (just + in Python). N.B. this also works because zip only processes until the end of the shortest list.

The first attempt

So I combined this all into the following recursive function:

def next_row(row, i):
    if i == 0:
        return row
    new_row = [1] + [x + y for x, y in zip(row, row[1:])] + [1]
    return next_row(new_row, i-1)

The great thing was that this code was almost completely perfect at solving the problem the very first time I wrote it. The only problem I had was that I had mistyped the 'tail' and written row[:1] instead of row[1:]. Once I fixed that the code worked perfectly. Plus that was an easy, 5 minute bug to fix.

This is actually really, really exciting for me. To have code that works (passed the tests (correct results time and) and was accepted as a submission) first time off is awesome. The big time drain that I hit when solving coding problems was if your solution doesn't work and having to bug fix things. This is what turns a 30 minute problem into an 4-10 hour problem.

The improved attempt

N.B. Anyone learning from this there are definite issues with this section - I'm mutating row. See the last section for more details. I'm leaving this here though to show the ugly backward steps I made.

I still wanted to try and improve this though. I think a 'smell' in functional programming is if you end up with an if statement in your code.

So I made a futher attempt by introducing a lambda:

class Solution:
    def getRow(self, A):
        process = lambda row: [1] + [x + y for x, y in zip(row, row[1:])] + [1]
        row = [1]
        for i in range(A):
            row = process(row)
        return row

This code again, worked perfectly. It would have suffered from the same 'tail' bug I had previously, but prevents the possibility of bug in the base case of the recursion.

This then becomes more similar to the Haskell:

nextRow vs = [1] ++ zipWith (+) vs (tail vs) ++ [1]
allPascals = iterate nextRow [1]

Conclusion

I still don't really know if this is more 'declarative'.

I've replaced

for i in range(A):
    pascal.append(0)
    for j in range(i,0,-1):
        pascal[j] += pascal[j-1]

with

process = lambda row: [1] + [x + y for x, y in zip(row, row[1:])] + [1]
for i in range(A):
    row = process(row)

It certainly is more similar to what the book suggested was 'declarative'. But I could have just sub-functioned the inner for loop of the imperitive solution.

What it does do is eliminate the middle for loop and reduce the various i,0,j-1,-1 elements which cause the bugs and are hard to track down.

In the functional code the only similar, 'off-by-one' style code is for row[1:] which is where my only bug appeared.

It is also useful that it effectively encourages you to create sub-functions.

So I still don't know what declarative really is, but the code I seem to write searching for it seems more robust.

Update

row = process(row) is not functional. It's mutating row. I realised this, but as part of my learning I couldn't think of a functional way of fixing it. Watching an OSCON video on Functional Thinking, I think that I actually need 'reduce' steadily build up the pascal row. This is work in progress...