199 lines
4.2 KiB
Python
199 lines
4.2 KiB
Python
'''Bell numbers'''
|
|
|
|
from itertools import accumulate, chain, islice
|
|
from operator import add, itemgetter
|
|
from functools import reduce
|
|
|
|
|
|
# bellNumbers :: [Int]
|
|
def bellNumbers():
|
|
'''Bell or exponential numbers.
|
|
A000110
|
|
'''
|
|
return map(itemgetter(0), bellTriangle())
|
|
|
|
|
|
# bellTriangle :: [[Int]]
|
|
def bellTriangle():
|
|
'''Bell triangle.'''
|
|
return map(
|
|
itemgetter(1),
|
|
iterate(
|
|
compose(
|
|
bimap(last)(identity),
|
|
list, uncurry(scanl(add))
|
|
)
|
|
)((1, [1]))
|
|
)
|
|
|
|
|
|
# ------------------------- TEST --------------------------
|
|
# main :: IO ()
|
|
def main():
|
|
'''Tests'''
|
|
showIndex = compose(repr, succ, itemgetter(0))
|
|
showValue = compose(repr, itemgetter(1))
|
|
print(
|
|
fTable(
|
|
'First fifteen Bell numbers:'
|
|
)(showIndex)(showValue)(identity)(list(
|
|
enumerate(take(15)(bellNumbers()))
|
|
))
|
|
)
|
|
|
|
print('\nFiftieth Bell number:')
|
|
bells = bellNumbers()
|
|
drop(49)(bells)
|
|
print(
|
|
next(bells)
|
|
)
|
|
|
|
print(
|
|
fTable(
|
|
"\nFirst 10 rows of Bell's triangle:"
|
|
)(showIndex)(showValue)(identity)(list(
|
|
enumerate(take(10)(bellTriangle()))
|
|
))
|
|
)
|
|
|
|
|
|
# ------------------------ GENERIC ------------------------
|
|
|
|
# bimap :: (a -> b) -> (c -> d) -> (a, c) -> (b, d)
|
|
def bimap(f):
|
|
'''Tuple instance of bimap.
|
|
A tuple of the application of f and g to the
|
|
first and second values respectively.
|
|
'''
|
|
def go(g):
|
|
def gox(x):
|
|
return (f(x), g(x))
|
|
return gox
|
|
return go
|
|
|
|
|
|
# compose :: ((a -> a), ...) -> (a -> a)
|
|
def compose(*fs):
|
|
'''Composition, from right to left,
|
|
of a series of functions.
|
|
'''
|
|
def go(f, g):
|
|
def fg(x):
|
|
return f(g(x))
|
|
return fg
|
|
return reduce(go, fs, identity)
|
|
|
|
|
|
# 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, tuple, str)):
|
|
return xs[n:]
|
|
else:
|
|
take(n)(xs)
|
|
return xs
|
|
return go
|
|
|
|
|
|
# fTable :: String -> (a -> String) ->
|
|
# (b -> String) -> (a -> b) -> [a] -> String
|
|
def fTable(s):
|
|
'''Heading -> x display function -> fx display function ->
|
|
f -> xs -> tabular string.
|
|
'''
|
|
def gox(xShow):
|
|
def gofx(fxShow):
|
|
def gof(f):
|
|
def goxs(xs):
|
|
ys = [xShow(x) for x in xs]
|
|
w = max(map(len, ys))
|
|
|
|
def arrowed(x, y):
|
|
return y.rjust(w, ' ') + ' -> ' + fxShow(f(x))
|
|
return s + '\n' + '\n'.join(
|
|
map(arrowed, xs, ys)
|
|
)
|
|
return goxs
|
|
return gof
|
|
return gofx
|
|
return gox
|
|
|
|
|
|
# identity :: a -> a
|
|
def identity(x):
|
|
'''The identity function.'''
|
|
return x
|
|
|
|
|
|
# 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 go
|
|
|
|
|
|
# last :: [a] -> a
|
|
def last(xs):
|
|
'''The last element of a non-empty list.'''
|
|
return xs[-1]
|
|
|
|
|
|
# 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.
|
|
'''
|
|
def go(a):
|
|
def g(xs):
|
|
return accumulate(chain([a], xs), f)
|
|
return g
|
|
return go
|
|
|
|
|
|
# succ :: Enum a => a -> a
|
|
def succ(x):
|
|
'''The successor of a value.
|
|
For numeric types, (1 +).
|
|
'''
|
|
return 1 + 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.
|
|
'''
|
|
def go(xs):
|
|
return (
|
|
xs[0:n]
|
|
if isinstance(xs, (list, tuple))
|
|
else list(islice(xs, n))
|
|
)
|
|
return go
|
|
|
|
|
|
# uncurry :: (a -> b -> c) -> ((a, b) -> c)
|
|
def uncurry(f):
|
|
'''A function over a tuple,
|
|
derived from a curried function.
|
|
'''
|
|
def go(tpl):
|
|
return f(tpl[0])(tpl[1])
|
|
return go
|
|
|
|
|
|
# MAIN ---
|
|
if __name__ == '__main__':
|
|
main()
|