'''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()