Catalan numbers/Pascal's triangle: Difference between revisions

===Procedural===

===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>