136 lines
3.1 KiB
Text
136 lines
3.1 KiB
Text
'''Padovan series'''
|
|
|
|
from itertools import chain, islice
|
|
from math import floor
|
|
from operator import eq
|
|
|
|
|
|
# padovans :: [Int]
|
|
def padovans():
|
|
'''Non-finite series of Padovan numbers,
|
|
defined in terms of recurrence relations.
|
|
'''
|
|
def recurrence(abc):
|
|
a, b, c = abc
|
|
return a, (b, c, a + b)
|
|
|
|
return unfoldr(recurrence)(
|
|
(1, 1, 1)
|
|
)
|
|
|
|
|
|
# padovanFloor :: [Int]
|
|
def padovanFloor():
|
|
'''The Padovan series, defined in terms
|
|
of a floor function.
|
|
'''
|
|
p = 1.324717957244746025960908854
|
|
s = 1.0453567932525329623
|
|
|
|
def f(n):
|
|
return floor(p ** (n - 1) / s + 0.5), 1 + n
|
|
|
|
return unfoldr(f)(0)
|
|
|
|
|
|
# padovanLSystem : [Int]
|
|
def padovanLSystem():
|
|
'''An L-system generating terms whose lengths
|
|
are the values of the Padovan integer series.
|
|
'''
|
|
def rule(c):
|
|
return 'B' if 'A' == c else (
|
|
'C' if 'B' == c else 'AB'
|
|
)
|
|
|
|
def f(s):
|
|
return s, ''.join(list(concatMap(rule)(s)))
|
|
|
|
return unfoldr(f)('A')
|
|
|
|
|
|
# ------------------------- TEST -------------------------
|
|
|
|
# prefixesMatch :: [a] -> [a] -> Bool
|
|
def prefixesMatch(xs, ys, n):
|
|
'''True if the first n items of each
|
|
series are the same.
|
|
'''
|
|
return all(map(eq, take(n)(xs), ys))
|
|
|
|
|
|
# main :: IO ()
|
|
def main():
|
|
'''Test three Padovan functions for
|
|
equivalence and expected results.
|
|
'''
|
|
print('\n'.join([
|
|
"First 20 padovans:\n",
|
|
repr(take(20)(padovans())),
|
|
|
|
"\nThe recurrence and floor-based functions" + (
|
|
" match over 64 terms:\n"
|
|
),
|
|
repr(prefixesMatch(
|
|
padovans(),
|
|
padovanFloor(),
|
|
64
|
|
)),
|
|
|
|
"\nFirst 10 L-System strings:\n",
|
|
repr(take(10)(padovanLSystem())),
|
|
|
|
"\nThe lengths of the first 32 L-System strings",
|
|
"match the Padovan sequence:\n",
|
|
repr(prefixesMatch(
|
|
padovans(),
|
|
(len(x) for x in padovanLSystem()),
|
|
32
|
|
))
|
|
]))
|
|
|
|
|
|
# ----------------------- GENERIC ------------------------
|
|
|
|
# concatMap :: (a -> [b]) -> [a] -> [b]
|
|
def concatMap(f):
|
|
'''A concatenated map'''
|
|
def go(xs):
|
|
return chain.from_iterable(map(f, xs))
|
|
return go
|
|
|
|
|
|
# unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
|
|
def unfoldr(f):
|
|
'''A lazy (generator) list unfolded from a seed value
|
|
by repeated application of f until no residue remains.
|
|
Dual to fold/reduce.
|
|
f returns either None, or just (value, residue).
|
|
For a strict output list, wrap the result with list()
|
|
'''
|
|
def go(x):
|
|
valueResidue = f(x)
|
|
while None is not valueResidue:
|
|
yield valueResidue[0]
|
|
valueResidue = f(valueResidue[1])
|
|
return go
|
|
|
|
|
|
# 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
|
|
|
|
|
|
# MAIN ---
|
|
if __name__ == '__main__':
|
|
main()
|