Pascal's triangle: Difference between revisions

Content added Content deleted

Inline

@@ 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'''.
-With a scanl and a zipWith to hand, we can derive both finite and non-finite lists of pascal rows from a single '''pascal''' step function:
+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>from itertools import (accumulate, chain, islice, starmap)
+<lang python>'''Pascal's triangle'''
+from itertools import (accumulate, chain, islice)
 from operator import (add)
-# pascal :: [Int] -> [Int]
+# nextPascal :: [Int] -> [Int]
-def pascal(xs):
+def nextPascal(xs):
+    '''A row of Pascal's triangle
+       derived from the previous row.'''
     return zipWith(add)([0] + xs)(xs + [0])
-# infinitePascalRows :: Generator [[Int]]
+# pascalTriangle :: Generator [[Int]]
-def infinitePascalRows():
+def pascalTriangle():
+    '''A non-finite stream of
-    return iterate(pascal)(
-        [1]
+       Pascal's triangle rows.'''
+    return iterate(nextPascal)([1])
-    )
-# nPascalRows :: Int -> [[Int]]
+# finitePascalRows :: Int -> [[Int]]
-def nPascalRows(n):
+def finitePascalRows(n):
+    '''The first n rows of Pascal's triangle.'''
-    return scanl(lambda a, _: pascal(a))(
-        [1]
+    def go(a, _):
+        return nextPascal(a)
-    )(enumFromTo(1)(n - 1))
+    return scanl(go)([1])(
+        range(1, n)
+    )
 # TESTS ---------------------------------------------------
 # main :: IO ()
 def main():
+    '''Test of two different approaches:
-    print (
+        - taking from a non-finite stream of rows
-        showPascal(
-            take(7)(
+        - constructing a finite list of rows'''
+    print(unlines(map(
-                infinitePascalRows()
-            )
+        showPascal,
-        )
+        [
+            take(7)(pascalTriangle()),  # Non finite,
-    )
+            finitePascalRows(7)         # finite.
-    print (
-        showPascal(
+        ]
+    )))
-            nPascalRows(7)
-        )
-    )
 # showPascal :: [[Int]] -> String
 def showPascal(xs):
+    '''Stringification of a list of
+       Pascal triangle rows.'''
     ys = list(xs)
@@ Line 4,169: / Line 4,176: @@
 # GENERIC -------------------------------------------------
 # center :: Int -> Char -> String -> String
 def center(n):
+    '''String s padded with c to approximate centre,
+       fitting in but not truncated to width n.
+    '''
     def go(c, s):
         qr = divmod(n - len(s), 2)
@@ Line 4,179: / Line 4,190: @@
-# ft :: (Int, Int) -> [Int]
+# 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):
+    '''An infinite list of repeated applications of f to x.'''
     def go(x):
         v = x
         while True:
-            yield(v)
+            yield v
             v = f(v)
     return lambda x: go(x)
-# scanl is like reduce, but returns a succession of
-# intermediate values, building from the left.
 # scanl :: (b -> a -> b) -> b -> [a] -> [b]
 def scanl(f):
+    '''scanl is like reduce, but returns a succession of
+       intermediate values, building from the left.'''
     return lambda a: lambda xs: (
         accumulate(chain([a], xs), f)
@@ Line 4,207: / Line 4,213: @@
 # take :: Int -> String -> String
 def take(n):
+    '''The prefix of xs of length n,
+       or xs itself if n > length xs.'''
     return lambda xs: (
         xs[0:n]
@@ Line 4,212: / Line 4,220: @@
         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]
 def zipWith(f):
+    '''A list constructed by zipping with a
+       custom function, rather than with the
+       default tuple constructor.'''
     return lambda xs: lambda ys: (
-        list(starmap(f, zip(xs, ys)))
+        list(map(f, xs, ys))
     )
+# MAIN ---
 if __name__ == '__main__':
     main()</lang>