convolve.py

from functools import reduce
from operator import mul
try:
   from math import prod
except ImportError:
   def prod(*C):
      return reduce(mul, C, 1)

def convolve(A, B, prod=prod, sum=sum):
    """Convolute A and B (often written A∗B)
    
    where A and B are lists.
    For example, if A are the coefficients of a polynomial p, starting with p[[1]], and B are the coefficients
    of a polynomial q, then convolve(A, B) is the list of coefiicients of the product pq.

    With C=A∗B: c[k] = ∑ a[i]*b[j], where the sum's domain is k=i+j

    Examples/tests::

        >>> convolve([1], [1])
        [1]
      
        >>> convolve([1,1,1], [1,1,1])
        [1, 2, 3, 2, 1]
      
        >>> convolve([1,-1], [0,0,1,1,1,1,1,1,0,0])
        [0, 0, 1, 0, 0, 0, 0, 0, -1, 0, 0]

        >>> convolve([0,1,2], [0,1,2])
        [0, 0, 1, 4, 4]

        >>> convolve(range(4), range(4))
        [0, 0, 1, 4, 10, 12, 9]

        >>> symbolic_calculations = dict(
        ...     prod=lambda *Q: "".join(map(str, Q)),
        ...     sum=lambda Q: "+".join(Q))

        >>> convolve([0,1,2], [0,1,2], **symbolic_calculations)
        ['00', '01+10', '02+11+20', '12+21', '22']

        >>> convolve(range(4), range(4), **symbolic_calculations)
        ['00', '01+10', '02+11+20', '03+12+21+30', '13+22+31', '23+32', '33']

        >>> convolve([0], range(4), **symbolic_calculations)
        ['00', '01', '02', '03']

        >>> convolve(range(4), [1], **symbolic_calculations)
        ['00', '10', '20', '30']
    """

    LA, LB = len(A), len(B)
    L = len(A) + len(B) - 1

    result = [0] * L
    for i in range(L):
        A_slice = A[:1+i]
        B_slice = B[i:i-L-1:-1]
        #print(f"{i}\t{A_slice}\t{B_slice}")
        result[i] = sum(map(prod, A_slice, B_slice))
    return result
    
if __name__ == "__main__":

    # this is a boundary case:
    Z = convolve([], [1,2,3,4,5])
    assert Z == convolve([1,2,3,4,5], [])
    assert 0 == sum(Z)

    import doctest
    doctest.testmod()