Using rank-2 types to eliminate constructor calls (Runar's code from http://paste.pocoo.org/show/463277/)

gistfile1.scala

import scalaz._
import Scalaz._

type G[A] = Forall[({type f[B] = ((A, B) => B, B) => B})#f]

val cons: Forall[({type f[A] = (A, Stream[A]) => Stream[A]})#f] =
  new Forall[({type f[A] = (A, Stream[A]) => Stream[A]})#f] {
    def apply[A] = (x, xs) => { println("called cons"); x #:: xs }
  }

val nil: Forall[Stream] = new Forall[Stream] {
  def apply[A] = { println("called nil"); Stream.empty[A] }
}

def build[A](g: G[A]): Stream[A] =
  g.apply(cons.apply, nil.apply)

def mapW[A, B](f: A => B, as: Stream[A]): G[B] = new G[B] {
  def apply [C] = (c, n) => as.foldRight(n)((a, b) => c(f(a), b))
}

def mapG[A, B](f: A => B, g: G[A]): G[B] = new G[B] {
  def apply[C] = (c, n) => g.apply((a: A, b: C) => c(f(a), b), n)
}

def map[A, B](f: A => B, as: Stream[A]): Stream[B] =
  build(mapW(f, as))

def any[A](p: A => Boolean, xs: Stream[A]) =
  mapW(p, xs).apply((a: Boolean, b: Boolean) => a || b, false)

def allEven[A](f: A => Int, as: Stream[A]) =
  mapG((x: Int) => x % 2 == 0, mapW(f, as)).apply((a: Boolean, b: Boolean) => a && b, true)