deepflatten.scala

/**
 * In a static language like scala, how could we repeatedly flatten a datastructure without reflection?
 * This is an interesting example of using implicit parameters to do the work for you.
 */
object DeepFlatten {

  // what should this really be called? ;)
  trait Flattenable[F[_]] {
    def flatten[A](f: F[F[A]]): F[A]
  }

  // here is how we flatten a couple of standard things:
  object Flattenable {
    implicit def option: Flattenable[Option] = new Flattenable[Option] {
      def flatten[A](f: Option[Option[A]]): Option[A] = f.getOrElse(None)
    }
    implicit def list: Flattenable[List] = new Flattenable[List] {
      def flatten[A](f: List[List[A]]): List[A] = f.flatten
    }
  }

  // Here is our deep flattener that goes from `F[A] => F[B]`
  sealed trait Flattener[F[_], A, B] {
    def apply(f: F[A]): F[B]
  }

  // now we have two ways of getting a Flattener
  trait FallbackFlattener {
    // The fallback way is to compose a flattener with a flattenable
    implicit def flattener2[F[_], A, B](implicit f: Flattenable[F], f1: Flattener[F, A, B]): Flattener[F, F[A], B] = new Flattener[F, F[A], B] {
      def apply(ffa: F[F[A]]): F[B] = f1(f.flatten(ffa))
    }
  }

  object Flattener extends FallbackFlattener {
    // The simplest way to get a Flattener is to just use a Flattenable:
    implicit def flatten[F[_], A](implicit f: Flattenable[F]): Flattener[F, F[A], A] =
      new Flattener[F, F[A], A] {
        def apply(a: F[F[A]]): F[A] = f.flatten(a)
      }
  }

  def deepFlatten[F[_], A, B](f: F[A])(implicit deep: Flattener[F, A, B]): F[B] =
    deep(f)

  /**
   * Now let's see it work. We have to give the result type since
   * there is no way to know how deep we want to go otherwise.
   */
  def test(): Unit = {
    // prints Some("hello")
    println(deepFlatten(Option(Option(Option("hello")))): Option[String])
    // prints List("hello")
    println(deepFlatten(List(List(List("hello")))): List[String])
    // prints List("a", "b", "c")
    println(deepFlatten(List(List(List("a", "b")), List(List("c")))): List[String])
  }
}