Skip to content

Instantly share code, notes, and snippets.

Embed
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()
.flatMap(CoProduct2::projectB)
.match(constantly(strictStack()),
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()
.flatMap(CoProduct2::projectB)
.match(constantly(io(strictStack())),
nz -> {
Fn1<Iterable<A>, A> convolveSample = zipWith(ring.multiplication(), hs.reverse()).fmap(ring.addition()::reduceLeft);
return sequence(map(work -> sequence(work, IO::io),
inGroupsOf(parallelism,
map(fn1(convolveSample::thunk).fmap(IO::io),
init(tails(concat(replicate(nz.intValue(), ring.addition().identity()), xs)))))),
IO::io)
.fmap(flatten())
.fmap(Shoki::strictQueue);
});
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment