Catalan numbers/Pascal's triangle: Difference between revisions
→{{header|Python}}: Added a functionally composed example.
Catskill549 (talk | contribs) |
(→{{header|Python}}: Added a functionally composed example.) |
||
Line 1,519:
=={{header|Python}}==
===Procedural===
{{trans|C++}}
<lang python>>>> n = 15
Line 1,543 ⟶ 1,544:
[1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</lang>
===Composition of pure functions===
Note that sequence A000108 on OEIS (referenced in the task description) confirms that the first four Catalan numbers are indeed 1, 1, 2, 5 ...
(Several scripts on this page appear to skip the first 1).
{{Trans|Haskell}}
{{Works with|Python|3.7}}
<lang python>'''Catalan numbers from Pascal's triangle'''
from itertools import (islice)
from operator import (add)
# nCatalans :: Int -> [Int]
def nCatalans(n):
'''The first n Catalan numbers,
derived from Pascal's triangle.'''
def diff(xs):
return (
xs[0] - (xs[1] if 1 < len(xs) else 0)
) if xs else None
return list(map(
compose(diff)(uncurry(drop)),
enumerate(map(fst, take(n)(
everyOther(
pascalTriangle()
)
)))
))
# pascalTriangle :: Gen [[Int]]
def pascalTriangle():
'''A non-finite stream of
Pascal's triangle rows.'''
return iterate(nextPascal)([1])
# nextPascal :: [Int] -> [Int]
def nextPascal(xs):
'''A row of Pascal's triangle
derived from a preceding row.'''
return zipWith(add)([0] + xs)(xs + [0])
# TEST ----------------------------------------------------
# main :: IO ()
def main():
'''First 16 Catalan numbers.'''
print(
nCatalans(16)
)
# GENERIC -------------------------------------------------
# compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
def compose(g):
'''Right to left function composition.'''
return lambda f: lambda x: g(f(x))
# drop :: Int -> [a] -> [a]
# drop :: Int -> String -> String
def drop(n):
'''The sublist of xs beginning at
(zero-based) index n.'''
def go(xs):
if isinstance(xs, list):
return xs[n:]
else:
take(n)(xs)
return xs
return lambda xs: go(xs)
# everyOther :: Gen [a] -> Gen [a]
def everyOther(g):
'''Every other item of a generator stream.'''
while True:
yield take(1)(g)
take(1)(g) # Consumed, not yielded.
# fst :: (a, b) -> a
def fst(tpl):
'''First component of a pair.'''
return tpl[0]
# iterate :: (a -> a) -> a -> Gen [a]
def iterate(f):
'''An infinite list of repeated applications of f to x.'''
def go(x):
v = x
while True:
yield v
v = f(v)
return lambda x: go(x)
# take :: Int -> [a] -> [a]
# 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]
if isinstance(xs, list)
else list(islice(xs, n))
)
# uncurry :: (a -> b -> c) -> ((a, b) -> c)
def uncurry(f):
'''A function over a tuple
derived from a curried function.'''
return lambda xy: f(xy[0])(
xy[1]
)
# 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(map(f, xs, ys))
)
# MAIN ---
if __name__ == '__main__':
main()</lang>
{{Out}}
<pre>[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</pre>
=={{header|Racket}}==
| |||