Skip to content

Instantly share code, notes, and snippets.

@anovstrup
Last active December 25, 2015 01:29
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save anovstrup/6894978 to your computer and use it in GitHub Desktop.
Save anovstrup/6894978 to your computer and use it in GitHub Desktop.
code related to issue 554
import scalaz._, Scalaz._, scalaz.effect._, scalaz.iteratee.{ Iteratee => I, _ }
import language.higherKinds
object Issue554 {
// Define a stream of n zero-filled arrays of size sz
def enumArrs[F[_]: Monad](sz: Int, n: Int) =
enumIterator1[Array[Byte], F](
Iterator.continually(Array.fill(sz)(0.toByte)).take(n))
// Define a stream of 2^16 64-KiB arrays;
// The size of the stream may need to be higher
// depending on your heap space.
def e[F[_]: Monad] = enumArrs[F](1 << 16, 1 << 17)
// Fold over the zipped/grouped stream, computing the
// total length of all the arrays.
def zipAndGroup[F[_]: Monad] = (I.fold[Stream[(Array[Byte], Long)], F, Long](0) {
_ + _.map(_._1.length).sum
} &= (e[F].zipWithIndex mapE I.group(4))).run
def zipAndGroup2[F[_]: Monad] = (I.fold[Stream[(Array[Byte], Long)], F, Long](0) {
_ + _.map(_._1.length).sum
} %= I.group(4) %= I.zipWithIndex &= e[F]).run
def zipAndGroup3[F[_]: Monad] = (I.fold[Stream[(Array[Byte], Long)], F, Long](0) {
_ + _.map(_._1.length).sum
} &= (e[F].zipWithIndex mapE I.take[(Array[Byte], Long), Stream](4).up[F].sequenceI)).run
def zipAndGroup4[F[_]: Monad] = (I.fold[Stream[(Array[Byte], Long)], F, Long](0) {
_ + _.map(_._1.length).sum
} %= I.group(4) %= zipWithIndex1 &= e[F]).run
def zipAndGroup5[F[_]: Monad] = (groupAndFold[F](4) &= e[F].zipWithIndex).run
def zipAndGroup6[F[_]: Monad] = (groupAndFold2[(Array[Byte], Long), F, Long](4)(0) { _ + _.map(_._1.length).sum } &= e[F].zipWithIndex).run
def zipAndGroup7[F[_]: Monad] = ((I.fold[Stream[(Array[Byte], Long)], F, Long](0) {
_ + _.map(_._1.length).sum
} %= I.group(4)) &= e[F].zipWithIndex).run
def zipAndGroup8[F[_]: Monad] = ((groupAndFold3[(Array[Byte], Long), Long](4)(0) { _ + _.map(_._1.length).sum }).up[F] &= e[F].zipWithIndex).run
def zipAndGroup9[F[_]: Monad] = (I.fold[Stream[(Array[Byte], Long)], F, Long](0) {
_ + _.map(_._1.length).sum
} &= (e[F].zipWithIndex mapE group1(4))).run
def zipAndFilter[F[_]: Monad] = (I.fold[(Array[Byte], Long), F, Long](0) {
_ + _._1.length
} &= (e[F].zipWithIndex mapE I.filter[(Array[Byte], Long), F](_ => true))).run
def filterAndGroup[F[_]: Monad] = (I.fold[Stream[Array[Byte]], F, Long](0) {
_ + _.map(_.length).sum
} &= (e[F] mapE I.filter[Array[Byte], F](_ => true) mapE I.group(4))).run
def groupOnly[F[_]: Monad] = (I.fold[Stream[Array[Byte]], F, Long](0) {
_ + _.map(_.length).sum
} &= (e[F] mapE I.group(4))).run
def zipOnly[F[_]: Monad] = (I.fold[(Array[Byte], Long), F, Long](0) {
_ + _._1.length
} &= e[F].zipWithIndex).run
def noZipOrGroup[F[_]: Monad] = (I.fold[Array[Byte], F, Long](0) {
_ + _.length
} &= e[F]).run
def groupAndFold[F[_]: Monad](n: Int): IterateeT[(Array[Byte], Long), F, Long] = {
def step(g: List[(Array[Byte], Long)], res: Long)(e: Input[(Array[Byte], Long)]): IterateeT[(Array[Byte], Long), F, Long] =
e.fold(el = el =>
if (g.size == n)
I.cont(step(List(el), res + g.map(_._1.length).sum))
else
I.cont(step(el :: g, res)), empty = I.cont(step(g, res)), eof = I.done(res + g.map(_._1.length).sum, I.eofInput))
I.cont(step(Nil, 0))
}
def groupAndFold2[E, F[_]: Monad, A](n: Int)(z: A)(f: (A, List[E]) => A): IterateeT[E, F, A] =
I.fold[E, F, (A, List[E])]((z, Nil)) {
case ((res, g), e) =>
if (g.size == n)
(f(res, g), List(e))
else
(res, e :: g)
} flatMap { case (res, g) => I.done(f(res, g), I.eofInput) }
def groupAndFold3[E, A](n: Int)(z: A)(f: (A, List[E]) => A): IterateeT[E, Id, A] =
I.fold[List[E], Id, A](z)(f) %= I.take[E, List](n).sequenceI
def enumIterator1[E, F[_]: Monad](x: => Iterator[E]): EnumeratorT[E, F] =
new EnumeratorT[E, F] {
def apply[A] = {
def go(xs: Iterator[E])(s: StepT[E, F, A]): IterateeT[E, F, A] =
if (xs.isEmpty) s.pointI
else {
s mapCont { k =>
val next = xs.next
k(I.elInput(next)) >>== go(xs)
}
}
go(x)
}
}
def zipWithIndex1[E, F[_]: Monad]: EnumerateeT[E, (E, Long), F] =
new EnumerateeT[E, (E, Long), F] {
def apply[A] = {
type StepEl = Input[(E, Long)] => IterateeT[(E, Long), F, A]
def loop(i: Long) = (step(i) _) andThen (I.cont[E, F, StepT[(E, Long), F, A]])
def step(i: Long)(k: StepEl): (Input[E] => IterateeT[E, F, StepT[(E, Long), F, A]]) = {
(in: Input[E]) =>
in.map(e => (e, i)).fold(
el = e => k(I.elInput(e)) >>== go(i + 1), empty = I.cont(step(i)(k)), eof = I.done(I.scont(k), in))
}
def go(i: Long) = I.doneOr(loop(i))
go(0)
}
}
def takeM[A, F[_], G[_]: Monad](n: Int)(implicit mon: Monoid[F[A]], pt: Applicative[F]): IterateeT[A, G, F[A]] = {
def loop(acc: F[A], n: Int)(s: Input[A]): IterateeT[A, G, F[A]] =
s(el = e =>
if (n <= 0) I.done[A, G, F[A]](acc, s)
else I.cont(loop(mon.append(acc, pt.point(e)), n - 1)),
empty = I.cont(loop(acc, n)),
eof = I.done[A, G, F[A]](acc, s))
I.cont(loop(mon.zero, n))
}
def group1[E, F[_], G[_]](n: Int)(implicit F: Applicative[F], FE: Monoid[F[E]], G: Monad[G]): EnumerateeT[E, F[E], G] =
takeM[E, F, G](n).sequenceI
}
@anovstrup
Copy link
Author

Issue554.zipAndGroup[IO].unsafePerformIO and Issue554.zipAndGroup[Free.Trampoline].run result in heap space errors.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment