flatMap exercise

fonad.scala

/**
 * Monad learning sandbox.
 * @author Allister MacLeod
 * Inspired by Tony Morris.
 */

/**
 * Monad interface (from Tony).
 */
trait Monad[F[_]] {
  def point[A](a: => A): F[A]
  def bind[A, B](f: A => F[B]): F[A] => F[B]
}


/**
 * Monad implicits.
 */
object Monad {
  implicit val ListMonad: Monad[List] = new Monad[List] {
    def point[A](a: => A): List[A] = List(a)
    def bind[A, B](f: A => List[B]): List[A] => List[B] = {
      (x: List[A]) =>
        x.flatMap(f)
    }
  }

  implicit val OptionMonad: Monad[Option] = new Monad[Option] {
    def point[A](a: => A): Option[A] = Some(a)
    def bind[A, B](f: A => Option[B]): Option[A] => Option[B] = {
      (x: Option[A]) =>
        x match {
          case None => None
          case Some(v) => f(v)
        }
    }
  }
  /* <dobblego> amacleod: def x[F[_]: Monad]: Monad[({type λ[α]=OptionT[F, α]})#λ] // correction */
  /* def ReaderMonad[T]: Monad[({type λ[α] = T => α})#λ] = error("todo") */

  def OptionTMonad[F[_]: Monad]: Monad[({type L[A] = OptionT[F, A]})#L] = new Monad[({type L[A] = OptionT[F, A]})#L] {
    def point[A](a: => A): OptionT[F, A] = OptionT(error("dunno"))
    def bind[A, B](f: A => OptionT[F, B]): OptionT[F, A] => OptionT[F, B] = error("dunno")
  }

  def Function1Monad[T]: Monad[({type L[A] = Function1[T, A]})#L] = new Monad[({type L[A] = Function1[T, A]})#L] {
    def point[A](a: => A): Function1[T, A] = (_: T) => a
    def bind[A, B](f: A => Function1[T, B]): Function1[T, A] => Function1[T, B] = {
      (g: Function1[T, A]) => (x: T) => f(g(x))(x)
    }
  }

  def ReaderMonad[T]: Monad[({type L[A] = T => A})#L] = new Monad[({type L[C] = T => C})#L] {
    def point[A](a: => A): T => A = (_: T) => a
    def bind[A, B](f: A => (T => B)): (T => A) => (T => B) = (g: T => A) => (x: T) => f(g(x))(x)
  }

  implicit val StringReaderMonad = ReaderMonad[String]
}


/**
 * Option flatMap exercise class.  Must implement flatMap.
 *
 * Tony denotes the kind of OptionT as (* -> *) -> * -> *
 */
case class OptionT[F[_], A](a: F[Option[A]]) {
  def flatMap[B](f: A => OptionT[F, B])(implicit m: Monad[F]): OptionT[F, B] = {
    OptionT(
      m.bind {
        (opt: Option[A]) =>
          opt match {
            case Some(x) =>
              f(x).a
            case None =>
              m.point(None: Option[B])
          }
      }.apply(a)
    )
  }
}


/**
 * ListT case class for sneaking lists into places.
 */
//case class ListT[F[_], A](a: F[List[A]]) {
//  def flatMap[B](f: A => ListT[F, B])(implicit m: Monad[F]): ListT[F, B] = {
//    def unpackAndTransform(v: List[A]): F[List[B]] = v match {
//      case Nil =>
//        m.point(Nil: List[B])
//      case x :: xs =>
//        error("dunno")
//    }
//    return ListT(thing)
//  }
//}


/**
 * Runner/test-case for monad OptionT flatMap.
 */
object fonad {
  /**
   * Identity container class for use with the "identify" monad.
   */
  case class Identity[A](thing: A)

  /**
   * Measure the length of a string.
   */
  def measureLength(x: String): OptionT[Identity, Int] = OptionT(Identity(Some(x.length)))

  /**
   * Turn a string into a list of optional characters, capitalizing
   * alphabet letters and yielding None for digits.
   */
  def glarble(x: String): OptionT[List, Char] = {
    OptionT(
      x.toList.map {
        case c if (c.isDigit) =>
          None
        case c if (c.isLetter) =>
          Some(c.toUpper)
        case c =>
          Some(c)
      }
    )
  }

  /**
   * Pull shenanigans with optional strings.
   */
  def yucko(x: String): OptionT[Option, String] = {
    OptionT(
      if (x.length % 2 == 0) {
        Some(None)
      } else if ("foo".equals(x)) {
        None
      } else {
        Some(Some(x.reverse))
      }
    )
  }

  /**
   * Show the before and after of some transformation.
   */
  def showTransformation[F[_], A, B](input: OptionT[F, A], function: A => OptionT[F, B])(implicit monad: Monad[F]) {
    println("%s -> %s".format(input.toString, input.flatMap(function).toString))
  }

  /**
   * Test OptionT's flatMap with an identity monad.
   */
  private def identityTest {
    val o1 = OptionT[Identity, String](Identity(Some("foo")))
    val o2 = OptionT[Identity, String](Identity(None))
    implicit val identityMonad: Monad[Identity] = new Monad[Identity] {
      def point[A](a: => A) = Identity(a)
      def bind[A, B](f: A => Identity[B]): Identity[A] => Identity[B] = {
        (x: Identity[A]) => f(x.thing)
      }
    }
    println("measureLength:")
    showTransformation(o1, measureLength)
    showTransformation(o2, measureLength)
  }

  /**
   * Test OptionT's flatMap with a list monad.
   */
  private def listTest {
    val o1 = OptionT[List, String](List(Some("foo"), Some("b1a2r")))
    val o2 = OptionT[List, String](List(None))
    val o3 = OptionT[List, String](List(Some("ba1z"), None, Some("fa3z")))
    println("glarble:")
    showTransformation(o1, glarble)
    showTransformation(o2, glarble)
    showTransformation(o3, glarble)
  }

  /**
   * Test OptionT's flatMap with an option monad.
   */
  private def optionTest {
    val o1 = OptionT[Option, String](Some(Some("foo")))
    val o2 = OptionT[Option, String](None)
    val o3 = OptionT[Option, String](Some(Some("quux")))
    val o4 = OptionT[Option, String](Some(Some("yum")))
    val o5 = OptionT[Option, String](Some(None))
    println("yucko:")
    showTransformation(o1, yucko)
    showTransformation(o2, yucko)
    showTransformation(o3, yucko)
    showTransformation(o4, yucko)
    showTransformation(o5, yucko)
  }

//  private def listListTest {
//    def reverso(s: String): ListT[Option, Char] = {
//      return ListT(Some(s.reverse.toList))
//    }
//    val l1 = ListT[Option, String](Some(List("foo")))
//    val l2 = ListT[Option, String](None)
//    val l3 = ListT[Option, String](Some(Nil))
//    val l4 = ListT[Option, String](Some(List("foo", "bar")))
//    println("reverso:")
//    showTransformation(l1, reverso) // ListT(Some(List('f', 'o', 'o')))
//    showTransformation(l2, reverso)
//    showTransformation(l3, reverso)
//    showTransformation(l4, reverso) // ListT(Some(List('f', 'o', 'o', 'b', 'a', 'r')))?
//  }

  private def stringReaderTest {
    def stringToMaybeInt(s: String): Option[Int] = try { Some(s.toInt)} catch { case _ => None }
    val zero = Monad.StringReaderMonad.point(0)
    def konst(n: Option[Int]) = Monad.StringReaderMonad.point(n)
    println("StringReaderMonad.point(0)(\"foo\") = %s".format(zero("foo")))
    val radify = Monad.StringReaderMonad.bind((a: Option[Int]) => (s: String) => a match {
      case None => None
      case Some(radix) => try {
        Some(Integer.parseInt(s, radix))
      } catch {
        case _ => None
      }
    })
    val x = radify(konst(Some(2)))("101010")
    println("radify(konst(2))(\"101010\") = %s".format(x))
    def intyIdentity(f: Int => Int): Int => Int = f
    val y = Monad.Function1Monad[Int].bind(intyIdentity)((a: Int) => (b: Int) => a + b)(7)
    println("join (+) 7 = '%s'".format(y))
    println("join (*) 7 = '%s'".format(Monad.Function1Monad[Int].bind(intyIdentity)((a: Int) => (b: Int) => a*b)(7)))
    val treblePerhaps = Monad.ReaderMonad[Int].bind(Monad.ReaderMonad[Int].bind(intyIdentity))
    val z = treblePerhaps((a: Int) => (b: Int) => (c: Int) => a + b + c)(7)
    println("bind(bind(identity)) doublePlus 7 = '%s'".format(z))
  }

  /**
   * Run test.
   */
  def main(args: Array[String]) {
    identityTest
    listTest
    optionTest
    stringReaderTest
  }
}

amacleod@clydesdale:~/src/scala$ scalac fonad.scala
fonad.scala:29: error: type mismatch;
found : OptionT.this.a.type (with underlying type F[Option[A]])
required: F[Option[A]]
val fob: F[Option[B]] = binding.apply(a)
^
one error found