Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

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...

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment