Functional Pascal triangle in Python (working version)

Question

This is actually a follow-up question of Yet another Pascal triangle in Python written in functional programming pattern, which is put on hold for posting broken code.

Again, this is my implementation of a Pascal program, which is used to print an n-order Pascal triangle. I write it to familiarize myself with Python's Functional Programming Modules. Some changes have been made to get the code work and make it more "functional"

#!/usr/bin/env python3
import operator
from itertools import starmap, tee
def pairwise(iterable):
 """
 s -> (s0,s1), (s1,s2), (s2,s3), ...
 https://docs.python.org/3/library/itertools.html#itertools-recipes
 """
 a, b = tee(iterable)
 next(b, None)
 return zip(a, b)
def pascal_row(n):
 """
 Return a generator that yields the nth row of a Pascal triangle
 """
 if n < 2:
 return (x for x in [1])
 else:
 def dispatch():
 yield 1
 yield from starmap(operator.add, pairwise(pascal_row(n-1)))
 yield 1
 return dispatch()
def print_pascal(n):
 """
 Print an n-order Pascal triangle
 """
 if n > 0:
 print_pascal(n-1)
 print(list(pascal_row(n)))
print_pascal(10)

Output:

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]

Please let me know if this piece of code isn't reflecting the essence of functional programming correctly.

Answer 1

Your current code calls pascal_row O(n^2) times (put a print inside to see this) through recursion. You don't want to be repeating so much calculation. To cache the results:

from functools import lru_cache
@lru_cache(maxsize=None)
def pascal_row(n):

However then you can't be returning generators anymore because after one iteration they'll be exhausted and yet the caching will return the same generators repeatedly, so you won't get the right results. This is fine, there wasn't really much use in the generators. It was particularly weird to see (x for x in [1]).

You could return list(dispatch()) but there's a much better itertools way than successive yielding: chain.

return list(chain([1], starmap(operator.add, pairwise(pascal_row(n - 1))), [1]))

But really there's no need for all this. The Pythonic way would be:

return [1] + [a + b for a, b in pairwise(pascal_row(n - 1))] + [1]

which is still decently functional.

if n < 2: implies that n might also be 0, -1, etc. You want to:

1. Make it clear to readers that n should not be that.
2. Make sure the program quickly ends in an error in such a case so that you can find the bug.

Therefore add an assert n == 1 in this case.

This comes out to:

@lru_cache(maxsize=None)
def pascal_row(n):
 """
 Return a list that yields the nth row of a Pascal triangle
 """
 if n < 2:
 assert n == 1
 return [1]
 else:
 return [1] + [a + b for a, b in pairwise(pascal_row(n - 1))] + [1]

In my opinion the recursion in print_pascal is completely unnecessary and a simple for loop would be much better, but I suppose you want it that way for the exercise.

To be really functional you could ensure that your data structures are immutable and use tuples instead of lists, although it's less pretty:

if n < 2:
 return (1,)
else:
 return (1,) + tuple(a + b for a, b in pairwise(pascal_row(n - 1))) + (1,)

• Graipher: Hey, welcome to Code Review! This is a nice first answer (first answer here, anyway...).
• ChatterOne: As I said in the other question about the same pascal triangle, try adding print(pascal_row.cache_info()) at the end of the code and see the cache misses

Answer 2

Main

You should add a main to this program (see this answer for more info)

if __name__ == '__main__':
 print_pascal(10)

Your printing is a bit strange.

I would either split up print_pascal or change it further, the output as it is is awkward. I would expect:

1
1, 1
1, 2, 1

or:

1
1 1
1 2 1

etc. The [] are weird. I would either create a function pascal(n) -> [[Row]] or format the printing to omit the brackets in print_pascal. The first method gives a datatype immediately by Python. The second option is more efficient.

Answer 3

I don't really have a lot of feedback on your code other than it feels awkward with things like

1. side effect next(b, None) in pairwise
2. starmap instead of list comprehension in pascal

They're not wrong but they just feel out of place to me. Here's how I might write your pascal program

def sliding (n,xs):
 if n > len(xs):
 return []
 else:
 return [xs[0:n]] + sliding(n, xs[1:])
def pascal (n):
 def loop (m, prev, k):
 if n == m:
 return k([prev])
 else:
 return loop(m + 1, [1] + [x + y for (x,y) in sliding(2, prev)] + [1], lambda rest: k([prev] + rest))
 return loop(1, [1], lambda x: x)
def print_pascal (n):
 [print(line) for line in pascal(n)]
print_pascal(10)
# [1]
# [1, 1]
# [1, 2, 1]
# [1, 3, 3, 1]
# [1, 4, 6, 4, 1]
# [1, 5, 10, 10, 5, 1]
# [1, 6, 15, 20, 15, 6, 1]
# [1, 7, 21, 35, 35, 21, 7, 1]
# [1, 8, 28, 56, 70, 56, 28, 8, 1]
# [1, 9, 36, 84, 126, 126, 84, 36, 9, 1]

---

Side-effecting print_pascal function is probably bad – maybe just leave it defined in continuation passing style

def sliding (n,xs):
 if n > len(xs):
 return []
 else:
 return [xs[0:n]] + sliding(n, xs[1:])
def pascalk (n,k):
 def loop (m, prev, k):
 if n == m:
 return k([prev])
 else:
 return loop(m + 1, [1] + [x + y for (x,y) in sliding(2, prev)] + [1], lambda rest: k([prev] + rest))
 return loop(1, [1], k)
pascalk(10, lambda rows: [print(row) for row in rows])
# [1]
# [1, 1]
# [1, 2, 1]
# [1, 3, 3, 1]
# [1, 4, 6, 4, 1]
# [1, 5, 10, 10, 5, 1]
# [1, 6, 15, 20, 15, 6, 1]
# [1, 7, 21, 35, 35, 21, 7, 1]
# [1, 8, 28, 56, 70, 56, 28, 8, 1]
# [1, 9, 36, 84, 126, 126, 84, 36, 9, 1]