Pascal's triangle: Difference between revisions
Content added Content deleted
(→Functional Python: pylinted for Python 3, tidied.) |
|||
Line 4,113: | Line 4,113: | ||
The itertools module yields a simple functional definition of '''scanl''' in terms of '''accumulate''' and '''chain''', and a similar definition of '''zipWith''' in terms of '''starmap'''. |
The itertools module yields a simple functional definition of '''scanl''' in terms of '''accumulate''' and '''chain''', and a similar definition of '''zipWith''' in terms of '''starmap'''. |
||
With a scanl and a zipWith to hand, we can derive both finite and non-finite lists of pascal rows from a single ''' |
With a scanl and a zipWith to hand, we can derive both finite and non-finite lists of pascal rows from a single '''nextPascal''' step function: |
||
{{Works with|Python|3.7}} |
|||
⚫ | |||
<lang python>'''Pascal's triangle''' |
|||
⚫ | |||
from operator import (add) |
from operator import (add) |
||
# |
# nextPascal :: [Int] -> [Int] |
||
def |
def nextPascal(xs): |
||
'''A row of Pascal's triangle |
|||
derived from the previous row.''' |
|||
return zipWith(add)([0] + xs)(xs + [0]) |
return zipWith(add)([0] + xs)(xs + [0]) |
||
# |
# pascalTriangle :: Generator [[Int]] |
||
def |
def pascalTriangle(): |
||
'''A non-finite stream of |
|||
⚫ | |||
Pascal's triangle rows.''' |
|||
⚫ | |||
⚫ | |||
# |
# finitePascalRows :: Int -> [[Int]] |
||
def |
def finitePascalRows(n): |
||
'''The first n rows of Pascal's triangle.''' |
|||
⚫ | |||
def go(a, _): |
|||
return nextPascal(a) |
|||
)(enumFromTo(1)(n - 1)) |
|||
⚫ | |||
⚫ | |||
⚫ | |||
# TESTS --------------------------------------------------- |
# TESTS --------------------------------------------------- |
||
# main :: IO () |
# main :: IO () |
||
def main(): |
def main(): |
||
'''Test of two different approaches: |
|||
⚫ | |||
- taking from a non-finite stream of rows |
|||
showPascal( |
|||
- constructing a finite list of rows''' |
|||
⚫ | |||
infinitePascalRows() |
|||
showPascal, |
|||
[ |
|||
take(7)(pascalTriangle()), # Non finite, |
|||
⚫ | |||
finitePascalRows(7) # finite. |
|||
print ( |
|||
] |
|||
⚫ | |||
nPascalRows(7) |
|||
⚫ | |||
⚫ | |||
# showPascal :: [[Int]] -> String |
# showPascal :: [[Int]] -> String |
||
def showPascal(xs): |
def showPascal(xs): |
||
'''Stringification of a list of |
|||
Pascal triangle rows.''' |
|||
ys = list(xs) |
ys = list(xs) |
||
Line 4,169: | Line 4,176: | ||
# GENERIC ------------------------------------------------- |
# GENERIC ------------------------------------------------- |
||
# center :: Int -> Char -> String -> String |
# center :: Int -> Char -> String -> String |
||
def center(n): |
def center(n): |
||
'''String s padded with c to approximate centre, |
|||
fitting in but not truncated to width n. |
|||
⚫ | |||
def go(c, s): |
def go(c, s): |
||
qr = divmod(n - len(s), 2) |
qr = divmod(n - len(s), 2) |
||
Line 4,179: | Line 4,190: | ||
# |
# iterate :: (a -> a) -> a -> Gen [a] |
||
def enumFromTo(m): |
|||
return lambda n: list(range(m, 1 + n)) |
|||
# iterate :: (a -> a) -> a -> Generator [a] |
|||
def iterate(f): |
def iterate(f): |
||
'''An infinite list of repeated applications of f to x.''' |
|||
def go(x): |
def go(x): |
||
v = x |
v = x |
||
while True: |
while True: |
||
yield |
yield v |
||
v = f(v) |
v = f(v) |
||
return lambda x: go(x) |
return lambda x: go(x) |
||
⚫ | |||
⚫ | |||
# scanl :: (b -> a -> b) -> b -> [a] -> [b] |
# scanl :: (b -> a -> b) -> b -> [a] -> [b] |
||
def scanl(f): |
def scanl(f): |
||
⚫ | |||
⚫ | |||
return lambda a: lambda xs: ( |
return lambda a: lambda xs: ( |
||
accumulate(chain([a], xs), f) |
accumulate(chain([a], xs), f) |
||
Line 4,207: | Line 4,213: | ||
# take :: Int -> String -> String |
# take :: Int -> String -> String |
||
def take(n): |
def take(n): |
||
'''The prefix of xs of length n, |
|||
or xs itself if n > length xs.''' |
|||
return lambda xs: ( |
return lambda xs: ( |
||
xs[0:n] |
xs[0:n] |
||
Line 4,212: | Line 4,220: | ||
else list(islice(xs, n)) |
else list(islice(xs, n)) |
||
) |
) |
||
# unlines :: [String] -> String |
|||
def unlines(xs): |
|||
'''A single string derived by the intercalation |
|||
of a list of strings with the newline character.''' |
|||
return '\n'.join(xs) |
|||
# zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] |
# zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] |
||
def zipWith(f): |
def zipWith(f): |
||
'''A list constructed by zipping with a |
|||
custom function, rather than with the |
|||
default tuple constructor.''' |
|||
return lambda xs: lambda ys: ( |
return lambda xs: lambda ys: ( |
||
list( |
list(map(f, xs, ys)) |
||
) |
) |
||
# MAIN --- |
|||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</lang> |
main()</lang> |