Trampolined to avoid stack overflow ...

build.sbt

libraryDependencies += "com.chuusai" %% "shapeless" % "2.2.0-RC1"

scalaVersion := "2.11.6"

Foldable.scala

import scala.util.control.TailCalls._

import shapeless._

trait Foldable[F[_]] {
  def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B): B
}

object Foldable {
  implicit def apply[F[_]](implicit fr: Lazy[FoldableRec[F]]): Foldable[F] =
    new Foldable[F] {
      def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B): B = fr.value.foldLeft(fa, b)(f).result
    }
}

trait FoldableRec[F[_]] {
  def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B): TailRec[B]
}

object FoldableRec extends FoldableRec0 {
  def apply[F[_]](implicit F: Lazy[FoldableRec[F]]): FoldableRec[F] = F.value

  implicit val idFoldableRec: FoldableRec[Id] =
    new FoldableRec[Id] {
      def foldLeft[A, B](fa: A, b: B)(f: (B, A) => B) =
        done(f(b, fa))
    }

  implicit def hcons[F[_]](implicit F: IsHCons1[F, FoldableRec, FoldableRec]): FoldableRec[F] =
    new FoldableRec[F] {
      override def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B) = {
        val (hd, tl) = F.unpack(fa)
        for {
          h <- F.fh.foldLeft(hd, b)(f)
          t <- F.ft.foldLeft(tl, h)(f)
        } yield t
      }
    }

  implicit def ccons[F[_]](implicit F: IsCCons1[F, FoldableRec, FoldableRec]): FoldableRec[F] =
    new FoldableRec[F] {
      def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B) =
        F.unpack(fa) match {
          case Left(l) =>
            tailcall(F.fh.foldLeft(l, b)(f))
          case Right(r) =>
            tailcall(F.ft.foldLeft(r, b)(f))
        }
    }

  implicit def generic[F[_]](implicit F: Generic1[F, FoldableRec]): FoldableRec[F] =
    new FoldableRec[F] {
      def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B) =
        tailcall(F.fr.foldLeft(F.to(fa), b)(f))
    }
}

sealed abstract class FoldableRec0 {
  implicit def constFoldableRec[T]: FoldableRec[Const[T]#λ] =
    new FoldableRec[Const[T]#λ] {
      override def foldLeft[A, B](fa: T, b: B)(f: (B, A) => B) =
        done(b)
    }
}

sealed abstract class IList[A]
final case class ICons[A](head: A, tail: IList[A]) extends IList[A]
final case class INil[A]() extends IList[A]

object DerivingFoldableExample {

  def main(args: Array[String]): Unit = {
    val list = (1 to 100000).foldLeft(ICons(0, INil())){ (acc, i) => ICons(i, acc) }

    println(Foldable[IList].foldLeft(list, 0)(_ + _))
  }
}