{{ message }}

Instantly share code, notes, and snippets.

# ianchanning/pascal-functional-learnings.md

Last active Dec 27, 2016

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 = 

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)```

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 =  ++ zipWith (+) vs (tail vs) ++ 
allPascals = iterate nextRow ```

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 `` 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 =  + [x + y for x, y in zip(row, row[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:  + [x + y for x, y in zip(row, row[1:])] + 
row = 
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 =  ++ zipWith (+) vs (tail vs) ++ 
allPascals = iterate nextRow ```

## 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:  + [x + y for x, y in zip(row, row[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...