Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
parallel / sequential convolution generalized to any algebraic ring
static interface CommutativeSemigroup<A> extends Semigroup<A> {
static interface CommutativeMonoid<A> extends CommutativeSemigroup<A>, Monoid<A> {
static interface Abelian<A> extends CommutativeMonoid<A> {
A inverse(A a);
static interface Ring<A> {
Abelian<A> addition();
Monoid<A> multiplication();
public static final class Convolution {
public static final <A> OrderedCollection<Natural, A> convolve(OrderedCollection<Natural, A> hs,
OrderedCollection<Natural, A> xs,
Ring<A> ring) {
return hs.sizeInfo().getSize().dec()
nz -> strictQueue(map(zipWith(ring.multiplication(), hs.reverse()).fmap(ring.addition()::reduceLeft),
init(tails(concat(replicate(nz.intValue(), ring.addition().identity()), xs))))));
public static final <A> IO<OrderedCollection<Natural, A>> parallelConvolve(OrderedCollection<Natural, A> hs,
OrderedCollection<Natural, A> xs,
Ring<A> ring,
int parallelism) {
return hs.sizeInfo().getSize().dec()
nz -> {
Fn1<Iterable<A>, A> convolveSample = zipWith(ring.multiplication(), hs.reverse()).fmap(ring.addition()::reduceLeft);
return sequence(map(work -> sequence(work, IO::io),
init(tails(concat(replicate(nz.intValue(), ring.addition().identity()), xs)))))),
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment