Bell numbers: Difference between revisions
→{{header|Python}}: Added a functionally composed draft.
(added Haskell implementation) |
(→{{header|Python}}: Added a functionally composed draft.) |
||
Line 1,393:
=={{header|Python}}==
===Procedural===
{{trans|D}}
<lang python>def bellTriangle(n):
Line 1,447 ⟶ 1,448:
[4140, 5017, 6097, 7432, 9089, 11155, 13744, 17007, 21147]
[21147, 25287, 30304, 36401, 43833, 52922, 64077, 77821, 94828, 115975]</pre>
===Functional===
{{Trans|Haskell}}
<lang 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(
lambda xs: (xs[-1], xs),
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-------------------------
# compose :: ((a -> a), ...) -> (a -> a)
def compose(*fs):
'''Composition, from right to left,
of a series of functions.
'''
return lambda x: reduce(
lambda a, f: f(a),
fs[::-1], 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, tuple, str)):
return xs[n:]
else:
take(n)(xs)
return xs
return lambda xs: go(xs)
# 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 go(xShow, fxShow, f, xs):
ys = [xShow(x) for x in xs]
w = max(map(len, ys))
return s + '\n' + '\n'.join(map(
lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)),
xs, ys
))
return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
xShow, fxShow, f, xs
)
# 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 lambda x: go(x)
# 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)
)
# 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.
'''
return lambda xs: (
xs[0:n]
if isinstance(xs, (list, tuple))
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 tpl: f(tpl[0])(tpl[1])
# MAIN ---
if __name__ == '__main__':
main()</lang>
{{Out}}
<pre>First fifteen Bell numbers:
1 -> 1
2 -> 1
3 -> 2
4 -> 5
5 -> 15
6 -> 52
7 -> 203
8 -> 877
9 -> 4140
10 -> 21147
11 -> 115975
12 -> 678570
13 -> 4213597
14 -> 27644437
15 -> 190899322
Fiftieth Bell number:
10726137154573358400342215518590002633917247281
First 10 rows of Bell's triangle:
1 -> [1]
2 -> [1, 2]
3 -> [2, 3, 5]
4 -> [5, 7, 10, 15]
5 -> [15, 20, 27, 37, 52]
6 -> [52, 67, 87, 114, 151, 203]
7 -> [203, 255, 322, 409, 523, 674, 877]
8 -> [877, 1080, 1335, 1657, 2066, 2589, 3263, 4140]
9 -> [4140, 5017, 6097, 7432, 9089, 11155, 13744, 17007, 21147]
10 -> [21147, 25287, 30304, 36401, 43833, 52922, 64077, 77821, 94828, 115975</pre>
=={{header|REXX}}==
| |||