Photo credit: cheers Hembo Pagi

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

- “say what you want” not “how to do it”
- picture vs recipie
`sqrt(2)`

vs looping from`x = 1`

finding the mean of`x`

and`2/x`

- SQL, Haskell vs C++, Java

This is what I understand about functional programming:

- no side-effects
- 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…