scala/ScalaBook/chapter-03/higherOrder.scala

def id[α](x: α) = x

case class Fix[F[_,_],α](out:F[α,Fix[F,α]]) 

trait BiFunctor[F[_,_]] {
  def bimap[α,β,γ,δ]: 
     (α => β) => (γ => δ) => F[α,γ] => F[β,δ]
  def fmap2[α,β,γ]: (β => γ) => F[α,β] => F[α,γ] = 
    bimap(id[α])
}

def cata[α,β,F[_,_]] (f: F[α,β] => β) (t: Fix[F,α])
                     (implicit ft: BiFunctor[F]): β =
  f(ft.fmap2(cata[α,β,F](f))(t.out))

def ana[α,β,F[_,_]](f: β => F[α,β])(x : β)
                   (implicit ft: BiFunctor[F]): Fix[F,α] =
  Fix[F,α](ft.fmap2(ana[α,β,F](f))(f(x)))

def hylo[α,β,γ,F[_,_]](f: α => F[γ,α])(g: F[γ,β] => β)
                      (x: α)(implicit ft: BiFunctor[F]): β =
  g(ft.fmap2(hylo[α,β,γ,F](f)(g))(f(x)))

def build[α,F[_,_]](f: {def apply[β]:(F[α,β] => β) => β} ) = 
  f.apply(Fix[F,α])


trait ListF[α,β]
case class Nil[α,β]() extends ListF[α,β]
case class Cons[α,β](hd:α, tl:β) extends ListF[α,β]

implicit object biList extends BiFunctor[ListF] {
  def bimap[α,β,γ,δ] = f => g => {    
    case Nil()       => Nil() 
    case Cons(x,xs)  => Cons(f(x),g(xs))
  } 
}

type List[α] = Fix[ListF,α]
def nil[α]:List[α]  = Fix[ListF,α](Nil())
def cons[α]  = (x:α) => 
               (xs : List[α]) => 
               Fix[ListF,α](Cons(x,xs))

def sumList = cata[Int,Int,ListF]  {
  case Nil()     => 0
  case Cons(x,xs) => x + xs
} _

println(sumList(cons(1)(cons(2)(nil))))