<commit_before>#! /usr/bin/env python
"""
Copyright (C) 2011 by <NAME>.
Released under the open source MIT license:
http://www.opensource.org/licenses/MIT

Power series representations in Python.
Based on http://doc.cat-v.org/bell_labs/squinting_at_power_series/squint.pdf.
Developed using Python 2.6.5. May not work in earlier versions since some
recent features and builtins are used.

This is a Python implementation of the pseudocode in the above paper by
Doug McIlroy. Back when the paper was first written, McIlroy noted that
languages with the key features needed for such an implementation were
not in common use. Things are certainly different now; the Python
implementation below is a fairly straightforward expression of the
algorithms in the paper, and it's fast, but McIlroy put a Haskell
implementation on the web in 2007 that's way more compact; see here:

http://www.cs.dartmouth.edu/~doug/powser.html

All of the Haskell definitions there are one-liners. But I like Python,
and AFAIK no one has done an implementation of this stuff in Python,
so here we go. :-)

In the doctests below, we test some properties of power series using the
example series defined later in this module; the specific series and
operations are described in the individual method and function docstrings.
We also test standard identities that particular series should satisfy, such
as the trig identities. Note that with appropriate series representations of
constants (like ``ONE``), all the identities are satisfied. Finally, we test
whether the series themselves, when treated as functions operating on other
series, give the expected results: for example, that EXP(X) == EXP, i.e.,
that the exponential series, when composed with the series representing x,
gives back itself (and similarly for other series).
    
    >>> ZERO = PowerSeries()
    >>> ONE = nthpower(0)
    >>> X = nthpower(1)
    >>> N = nseries()
    >>> H = harmonicseries()
    >>> AH = altharmonicseries()
    >>> EXP = expseries()
    >>> SIN = sinseries()
    >>> COS = cosseries()
    >>> TAN = tanseries()
    >>> SEC = secseries()
    >>> ARCSIN = arcsinseries()
    >>> ARCTAN = arctanseries()
    >>> SINH = sinhseries()
    >>> COSH = coshseries()
    >>> TANH = tanhseries()
    >>> SECH = sechseries()
    >>> ARCSINH = arcsinhseries()
    >>> ARCTANH = arctanhseries()
    >>> allseries = [S for S in globals().values() if isinstance(S, PowerSeries)]
    >>> testseries = allseries
    >>> all(s == s.xmul.tail for s in testseries)
    True
    >>> all(s == s.head + s.tail.xmul for s in testseries)
    True
    >>> all(s == s + ZERO for s in testseries)
    True
    >>> all(s == ZERO + s for s in testseries)
    True
    >>> all(s == s * ONE for s in testseries)
    True
    >>> all(s == ONE * s for s in testseries)
    True
    >>> all(s == s / ONE for s in testseries)
    True
    >>> all(s == integ(deriv(s), s.zero) for s in testseries)
    True
    >>> all(s == deriv(integ(s)) for s in testseries)
    True
    >>> all(s(X) == s for s in testseries)
    True
    >>> testseries = [S for S in allseries if S.zero != 0]
    >>> all(s * (ONE / s) == ONE for s in testseries)
    True
    >>> testseries = [S for S in allseries if S.zero == 0 and S is not ZERO]
    >>> all(inv(inv(s)) == s for s in testseries)
    True
    >>> all(s(inv(s)) == X for s in testseries)
    True
    >>> inv(X) == X
    True
    >>> exp(ZERO) == ONE
    True
    >>> EXP(ZERO) == ONE
    True
    >>> exp(X) == EXP
    True
    >>> exp(-X) == ONE / EXP
    True
    >>> (SIN * SIN) + (COS * COS) == ONE
    True
    >>> ONE + (TAN * TAN) == (SEC * SEC)
    True
    >>> TWO = Fraction(2, 1) * ONE
    >>> (exp(X) + exp(-X)) / TWO == COSH
    True
    >>> (exp(X) - exp(-X)) / TWO == SINH
    True
    >>> (COSH * COSH) - (SINH * SINH) == ONE
    True
    >>> ONE - (TANH * TANH) == (SECH * SECH)
    True
    
"""

from fractions import Fraction
from itertools import count, islice, izip, izip_longest
from math import factorial

from memoize_generator import memoize_generator


class PowerSeries(object):
    """Power series encapsulation.
    
    Represents a power series as an iterable of coefficients; the nth
    term is the coefficient of x**n. The internal representation is a
    generator that yields the coefficients one by one. Operations on
    the series are implemented as construction of new generator
    functions in terms of existing ones.
    """
    
    testlimit = 10
    
    def __init__(self, f=None, g=None, l=None):
        """Construct a PowerSeries from a term function, generator, or list.
        
        If ``f`` is given, construct the series using ``f`` as the "term
        function"; internally, the function is used to construct a generator
        that represents the series.
        
        If ``g`` is given, construct the series using ``g`` as its generator.
        
        If ``l`` is given, construct a finite series with terms from ``l`` in
        order.
        
        If none of ``f``, ``g``, ``l`` is present, the series will be empty.
        """
        if g:
            self.__g = g
        elif f:
            def _g():
                for n in count():
                    yield f(n)
            self.__g = _g
        elif l:
            def _l():
                for n in xrange(len(l)):
                    yield l[n]
            self.__g = _l
        else:
            # Empty series
            self.__g = None
    
    @memoize_generator
    def _gen(self):
        """The full generator for this series.
        
        This method is for internal use only; the series generator should be
        accessed publicly via the ``__iter__`` method (or anything that uses
        it, such as a ``for`` loop).
        
        Note that we add an extra loop at the end of the series to yield zero
        elements forever if our own generator exhausts itself. This allows
        every series to look infinite when needed without requiring repetitive
        code in generators.
        
        Note also that we "memoize" our generator so that, if it is realized
        multiple times, the terms don't have to be recomputed. This provides
        a dramatic speedup since computing an operation like multiplication
        requires many realizations of the generator.
        """
        if self.__g:
            for term in self.__g():
                yield term
        while True:
            yield Fraction(0, 1)
    
    def __iter__(self):
        """Return an iterator over the series.
        
        This makes a ``PowerSeries`` an iterable, which combined with the
        properties below makes the notation simple.
        """
        return self._gen()
    
    def __eq__(self, other):
        """Test PowerSeries for equality.
        
        Obviously we can't do this perfectly since we would have to check a
        potentially infinite number of terms. The class field ``testlimit``
        determines how many terms we check; it defaults to 10 as a reasonable
        compromise (the doctests run quickly but we are still seeing at least
        5 nonzero terms for comparison even for series like sine and cosine
        where every other term is zero).
        
        Note that if two instances are compared which have the ``testlimit``
        field set to different values, the left object in the comparison
        determines the limit.
        """
        if isinstance(other, PowerSeries):
            return all(s == o for s, o in islice(izip(self, other), self.testlimit))
        return NotImplemented
    
    def __ne__(self, other):
        return not self == other
    
    # PowerSeries instances can't be hashed because that would require series that<commit_msg>Added note about not memoizing __iter__.<commit_after>#! /usr/bin/env python
"""
Copyright (C) 2011 by <NAME>.
Released under the open source MIT license:
http://www.opensource.org/licenses/MIT

Power series representations in Python.
Based on http://doc.cat-v.org/bell_labs/squinting_at_power_series/squint.pdf.
Developed using Python 2.6.5. May not work in earlier versions since some
recent features and builtins are used.

This is a Python implementation of the pseudocode in the above paper by
<NAME>. Back when the paper was first written, McIlroy noted that
languages with the key features needed for such an implementation were
not in common use. Things are certainly different now; the Python
implementation below is a fairly straightforward expression of the
algorithms in the paper, and it's fast, but McIlroy put a Haskell
implementation on the web in 2007 that's way more compact; see here:

http://www.cs.dartmouth.edu/~doug/powser.html

All of the Haskell definitions there are one-liners. But I like Python,
and AFAIK no one has done an implementation of this stuff in Python,
so here we go. :-)

In the doctests below, we test some properties of power series using the
example series defined later in this module; the specific series and
operations are described in the individual method and function docstrings.
We also test standard identities that particular series should satisfy, such
as the trig identities. Note that with appropriate series representations of
constants (like ``ONE``), all the identities are satisfied. Finally, we test
whether the series themselves, when treated as functions operating on other
series, give the expected results: for example, that EXP(X) == EXP, i.e.,
that the exponential series, when composed with the series representing x,
gives back itself (and similarly for other series).
    
    >>> ZERO = PowerSeries()
    >>> ONE = nthpower(0)
    >>> X = nthpower(1)
    >>> N = nseries()
    >>> H = harmonicseries()
    >>> AH = altharmonicseries()
    >>> EXP = expseries()
    >>> SIN = sinseries()
    >>> COS = cosseries()
    >>> TAN = tanseries()
    >>> SEC = secseries()
    >>> ARCSIN = arcsinseries()
    >>> ARCTAN = arctanseries()
    >>> SINH = sinhseries()
    >>> COSH = coshseries()
    >>> TANH = tanhseries()
    >>> SECH = sechseries()
    >>> ARCSINH = arcsinhseries()
    >>> ARCTANH = arctanhseries()
    >>> allseries = [S for S in globals().values() if isinstance(S, PowerSeries)]
    >>> testseries = allseries
    >>> all(s == s.xmul.tail for s in testseries)
    True
    >>> all(s == s.head + s.tail.xmul for s in testseries)
    True
    >>> all(s == s + ZERO for s in testseries)
    True
    >>> all(s == ZERO + s for s in testseries)
    True
    >>> all(s == s * ONE for s in testseries)
    True
    >>> all(s == ONE * s for s in testseries)
    True
    >>> all(s == s / ONE for s in testseries)
    True
    >>> all(s == integ(deriv(s), s.zero) for s in testseries)
    True
    >>> all(s == deriv(integ(s)) for s in testseries)
    True
    >>> all(s(X) == s for s in testseries)
    True
    >>> testseries = [S for S in allseries if S.zero != 0]
    >>> all(s * (ONE / s) == ONE for s in testseries)
    True
    >>> testseries = [S for S in allseries if S.zero == 0 and S is not ZERO]
    >>> all(inv(inv(s)) == s for s in testseries)
    True
    >>> all(s(inv(s)) == X for s in testseries)
    True
    >>> inv(X) == X
    True
    >>> exp(ZERO) == ONE
    True
    >>> EXP(ZERO) == ONE
    True
    >>> exp(X) == EXP
    True
    >>> exp(-X) == ONE / EXP
    True
    >>> (SIN * SIN) + (COS * COS) == ONE
    True
    >>> ONE + (TAN * TAN) == (SEC * SEC)
    True
    >>> TWO = Fraction(2, 1) * ONE
    >>> (exp(X) + exp(-X)) / TWO == COSH
    True
    >>> (exp(X) - exp(-X)) / TWO == SINH
    True
    >>> (COSH * COSH) - (SINH * SINH) == ONE
    True
    >>> ONE - (TANH * TANH) == (SECH * SECH)
    True
    
"""

from fractions import Fraction
from itertools import count, islice, izip, izip_longest
from math import factorial

from memoize_generator import memoize_generator


class PowerSeries(object):
    """Power series encapsulation.
    
    Represents a power series as an iterable of coefficients; the nth
    term is the coefficient of x**n. The internal representation is a
    generator that yields the coefficients one by one. Operations on
    the series are implemented as construction of new generator
    functions in terms of existing ones.
    """
    
    testlimit = 10
    
    def __init__(self, f=None, g=None, l=None):
        """Construct a PowerSeries from a term function, generator, or list.
        
        If ``f`` is given, construct the series using ``f`` as the "term
        function"; internally, the function is used to construct a generator
        that represents the series.
        
        If ``g`` is given, construct the series using ``g`` as its generator.
        
        If ``l`` is given, construct a finite series with terms from ``l`` in
        order.
        
        If none of ``f``, ``g``, ``l`` is present, the series will be empty.
        """
        if g:
            self.__g = g
        elif f:
            def _g():
                for n in count():
                    yield f(n)
            self.__g = _g
        elif l:
            def _l():
                for n in xrange(len(l)):
                    yield l[n]
            self.__g = _l
        else:
            # Empty series
            self.__g = None
    
    @memoize_generator
    def _gen(self):
        """The full generator for this series.
        
        This method is for internal use only; the series generator should be
        accessed publicly via the ``__iter__`` method (or anything that uses
        it, such as a ``for`` loop).
        
        Note that we add an extra loop at the end of the series to yield zero
        elements forever if our own generator exhausts itself. This allows
        every series to look infinite when needed without requiring repetitive
        code in generators.
        
        Note also that we "memoize" our generator so that, if it is realized
        multiple times, the terms don't have to be recomputed. This provides
        a dramatic speedup since computing an operation like multiplication
        requires many realizations of the generator.
        """
        if self.__g:
            for term in self.__g():
                yield term
        while True:
            yield Fraction(0, 1)
    
    def __iter__(self):
        """Return an iterator over the series.
        
        This makes a ``PowerSeries`` an iterable, which combined with the
        properties below makes the notation simple.
        
        Note that we do *not* memoize this method directly; we factor out
        the memoized generator and just realize it here. This is because
        ``__iter__`` is a special method that is handled differently by
        Python, so decorators don't work properly with it.
        """
        return self._gen()
    
    def __eq__(self, other):
        """Test PowerSeries for equality.
        
        Obviously we can't do this perfectly since we would have to check a
        potentially infinite number of terms. The class field ``testlimit``
        determines how many terms we check; it defaults to 10 as a reasonable
        compromise (the doctests run quickly but we are still seeing at least
        5 nonzero terms for comparison even for series like sine and cosine
        where every other term is zero).
        
        Note that if two instances are compared which have the ``testlimit``
        field set to different values, the left object in the comparison
        determines the limit.
        """
        if isinstance(other, PowerSeries):
            return all(s == o for s, o in islice(izip(self, other), self.testlimit))
        return NotImplemented
    
    def __ne__(self, other):
        return not self == other
    
    # PowerSeries instances can't be hashed because that would require series that
{'fraction_non_alphanumeric': 0.0935242681535927, 'fraction_numerical': 0.0030414396147509823, 'mean_word_length': 2.4059128182995253, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 294, 'https://': 0, 'lorem ipsum': 0, 'www.': 4, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1821482', 'n_tokens_mistral': 4487, 'n_tokens_neox': 4369, 'n_words': 1956}