Based on Eric Merten's solution to "A practical Haskell puzzle". http://www.haskell.org/pipermail/haskell-cafe/2011-March/089802.html

stack.scala

trait Category[Cat[-_,+_]] {
  def id[A]: Cat[A, A]
  def andThen[A, B, C](f: Cat[A, B], g: Cat[B, C]): Cat[A, C]
}

object Category {
  implicit object CategoryFunction1 extends Category[Function1] {
    def id[A]: A => A = a => a
    def andThen[A, B, C](f: A => B, g: B => C): A => C = f andThen g
  }
}

abstract class F[P[-_, +_], -B, +C](implicit Cat: Category[P]) {
  type Self[-_, +_] <: F[P, _, _]
  def ::[A](g: P[A, B]): Self[A, C]
  def ++[A](g: Self[C, A]): Self[B, A]
  def flatten: P[B, C]

  protected val cat = Cat
}

sealed trait Fun[-B, +C] extends F[Function1, B, C] {
  import Fun._

  type Self[-F, +G] = Fun[F, G]

  def ::[A](g: A => B): Fun[A, C] = Cons(g, this)
}

object Fun {
  case class Id[A]() extends Fun[A, A] {
    def flatten = cat.id
    def ++[Z](g: Fun[A, Z]) = g
  }

  case class Cons[A, B, C](g: A => B, f: Fun[B, C]) extends Fun[A, C] { self =>
    def flatten = cat.andThen(g, f.flatten)
    def ++[D](h: Fun[C, D]) = Cons(g, f match {
      case Id() => f ++ h
      case Cons(a, b) => Cons(a, b ++ h)
    })
  }
}

object Main {
  import Fun._

  val x = { x: String => 4 } :: { x: Int => Some(1) } :: Id()
  val y = { _: Option[Int] => "hello" } :: Id()
  val z = x ++ y
}