λ Tony’s blog λ

// Scala version 2.8.0.final
// http://scala-tools.org/repo-releases/org/scala-tools/testing/scalacheck_2.8.0/1.7/scalacheck_2.8.0-1.7.jar
 
 
/*
 
  PART 1
  ======
  Below are 15 exercises numbered 1 to 15. The task is to emulate the scala.Option API
  without using Some/None subtypes, but instead using a fold (called a
  catamorphism).
 
  A couple of functions are already done (map, get)
  to be used as an example. ScalaCheck tests are given below to
  verify the work. The desired result is to have all tests passing.
 
  The 15th exercise is not available in the existing Scala API so
  instructions are given in the comments.
 
 
  Part 2
  ======
 
  Below are 10 exercises numbered 16 to 25. The task is to implement additional
  methods for the Optional data type. These methods are not provided in the
  scala.Option API so to determine the correct result requires reading the method
  type signature and ensuring that the tests pass.
 
  The 25th exercise is notable in that its signature says nothing about
  scala.Option yet it is usable for Option (see the test for example).
 
 
  Revision History
  ================
 
  23/08/2010
  * Initial revision
 
  ----------------
 
  23/08/2010
  * Fixed prop_getOrElse. Thanks Michael Bayne.
 
  ----------------
 
  26/08/2010
  * Add lazy annotation to orElse method.
 
  ----------------
 
  01/09/2010
  Added Part 2
 
  02/09/2010
  * Fixed mapOptionals test (why wasn't it failing?). Thanks Alec Zorab.
  * Added comments including *** special note ***
 
*/
 
 
trait Optional[A] {
  // single abstract method
  def fold[X](some: A => X, none: => X): X
 
  import Optional._
 
  // Done for you.
  def map[B](f: A => B): Optional[B] =
    fold(f andThen some, none[B])
 
  // Done for you.
  // WARNING: undefined for None
  def get: A =
    fold(a => a, error("None.get"))
 
  // Exercise 1
  def flatMap[B](f: A => Optional[B]): Optional[B] =
    fold(f, none)
 
  // Exercise 2
  // Rewrite map but use flatMap, not fold.
  def mapAgain[B](f: A => B): Optional[B] =
    flatMap(f andThen some)
 
  // Exercise 3
  def getOrElse(e: => A): A =
    fold(s => s, e)
 
  // Exercise 4
  def filter(p: A => Boolean): Optional[A] =
    fold(a => if(p(a)) some(a) else none, none)
 
  // Exercise 5
  def exists(p: A => Boolean): Boolean =
    fold(p, false)
 
  // Exercise 6
  def forall(p: A => Boolean): Boolean =
    fold(p, true)
 
  // Exercise 7
  def foreach(f: A => Unit): Unit =
    fold(f, ())
 
  // Exercise 8
  def isDefined: Boolean =
    fold(_ => true, false)
 
  // Exercise 9
  def isEmpty: Boolean =
    fold(_ => false, true)
 
  // Exercise 10
  def orElse(o: => Optional[A]): Optional[A] =
    fold(_ => this, o)
 
  // Exercise 11
  def toLeft[X](right: => X): Either[A, X] =
    fold(Left(_), Right(right))
 
  // Exercise 12
  def toRight[X](left: => X): Either[X, A] =
    fold(Right(_), Left(left))
 
  // Exercise 13
  def toList: List[A] =
    fold(List(_), Nil)
 
  // Exercise 14
  def iterator: Iterator[A] =
    fold(Iterator.single(_), Iterator.empty)
 
  // Exercise 15 The Clincher!
  // Return a none value if either this or the argument is none.
  // Otherwise apply the function to the argument in some.
  // Don't be afraid to use functions you have written.
  // Better style, more points!
  def applic[B](f: Optional[A => B]): Optional[B] =
    f flatMap map
 
  // Utility
  def toOption: Option[A] = fold(Some(_), None)
 
  // Utility
  override def toString = 
    fold("some[" + _ + "]", "none")
 
  // Utility
  override def equals(o: Any) =
    o.isInstanceOf[Optional[_]] && {
      val q = o.asInstanceOf[Optional[_]]
      fold(a => q.exists(a == _),
           q.isEmpty)
    }
}
 
object Optional {
  // Done for you
  def none[A]: Optional[A] = new Optional[A] {
    def fold[X](some: A => X, none: => X) = none
  }
 
  // Done for you
  def some[A](a: A): Optional[A] = new Optional[A] {
    def fold[X](some: A => X, none: => X) = some(a)
  }
 
  // Utility
  def fromOption[A](o: Option[A]): Optional[A] = o match {
    case None    => none
    case Some(a) => some(a)
  }
 
  // *** Special note ***
  // Some of these functions are likely to be familiar List functions,
  // but with one specific distinction: in every covariant value appearing in
  // the type signature, this value is wrapped in Optional.
  // For example, the unwrapped:
  // filter:          (A => Boolean) => List[A] => List[A]
  // and the wrapped:
  // filterOptionals: (A => Optional[Boolean]) => List[A] => Optional[List[A]]
  // 
  // There are other functions of a similar nature below.
 
  // Exercise 16
  // If a none is encountered, then return a none, otherwise,
  // accumulate all the values in Optional.
  def mapOptionals[A, B](f: A => Optional[B], a: List[A]): Optional[List[B]] =
    error("todo")
 
  // Exercise 17
  // If a none is encountered, then return a none, otherwise,
  // accumulate all the values in Optional.
  def sequenceOptionals[A](a: List[Optional[A]]): Optional[List[A]] =
    error("todo")
 
  // Exercise 18
  // Use sequenceOptionals
  def mapOptionalsAgain[A, B](f: A => Optional[B], a: List[A]): Optional[List[B]] =
    error("todo")
 
  // Exercise 19 
  // Use mapOptionals
  def sequenceOptionalsAgain[A](a: List[Optional[A]]): Optional[List[A]] =
    error("todo")
 
  // Exercise 20
  // If a none is encountered, return none, otherwise,
  // flatten/join by one level.
  def joinOptionals[A](a: Optional[Optional[A]]): Optional[A] =
    error("todo")
 
  // Exercise 21
  def filterOptionals[A](p: A => Optional[Boolean], a: List[A]): Optional[List[A]] =
    error("todo")
 
  // Exercise 22
  def fillOptionals[A](n: Int, a: Optional[A]): Optional[List[A]] =
    error("todo")
 
  // Exercise 23
  // Use sequenceOptionals
  def fillOptionalsAgain[A](n: Int, a: Optional[A]): Optional[List[A]] =
    error("todo")
 
  // Exercise 24
  // Methods mentioning Optional in the type signature are prohibited, except applic and map
  def mapOptionalsYetAgain[A, B](f: A => Optional[B], a: List[A]): Optional[List[B]] =
    error("todo")
 
  // Consider: def joinOptional[A](a: Optional[Optional[A]]): Optional[A]
  // This function "flattens" the Optional into a Some value if possible.
  // It is not possible to write this using only applic and map (try it!).
 
  // Bye bye Option-specificity!
  // (setting up for Exercise 25)
  trait Applic[F[_]] {
    def point[A](a: A): F[A]
    def applic[A, B](f: F[A => B], a: F[A]): F[B]
 
    final def map[A, B](f: A => B, a: F[A]): F[B] =
      applic(point(f), a)
  }
 
  object Applic {
    implicit val OptionalApplic: Applic[Optional] = new Applic[Optional] {
      def point[A](a: A): Optional[A] = some(a)
      def applic[A, B](f: Optional[A => B], a: Optional[A]): Optional[B] = a applic f
    }
  }
 
  // Exercise 25
  // The Double-Clincher!
  def mapWhatever[A, B, F[_]](f: A => F[B], a: List[A])(implicit z: Applic[F]): F[List[B]] =
    error("todo")
}
 
import org.scalacheck._
import Arbitrary.arbitrary
import Prop._
 
object TestOptional extends Properties("Optional") {
  import Optional._
 
  implicit def ArbitraryOptional[A](implicit a: Arbitrary[A]): Arbitrary[Optional[A]] =
    Arbitrary(arbitrary[Option[A]] map fromOption)
 
  property("map") = forAll ((o: Optional[Int], f: Int => String) =>
    (o map f).toOption == (o.toOption map f))
 
  property("get") = forAll((o: Optional[Int]) =>
    o.isDefined ==>
      (o.get == o.toOption.get))
 
  property("flatMap") = forAll((o: Optional[Int], f: Int => Optional[String]) =>
    (o flatMap f).toOption == (o.toOption flatMap (f(_).toOption)))
 
  property("mapAgain") = forAll ((o: Optional[Int], f: Int => String) =>
    (o mapAgain f).toOption == (o map f).toOption)
 
  property("getOrElse") = forAll ((o: Optional[Int], n: Int) =>
    (o getOrElse n) == (o.toOption getOrElse n))
 
  property("filter") = forAll ((o: Optional[Int], f: Int => Boolean) =>
    (o filter f).toOption == (o.toOption filter f))
 
  property("exists") = forAll ((o: Optional[Int], f: Int => Boolean) =>
    (o exists f) == (o.toOption exists f))
 
  property("forall") = forAll ((o: Optional[Int], f: Int => Boolean) =>
    (o forall f) == (o.toOption forall f))
 
  property("foreach") = forAll ((o: Optional[Int], f: Int => Unit, n: Int) => {
    var x: Int = n
    var y: Int = x
 
    o foreach (t => x = x + t)
    o.toOption foreach (t => y = y + t)
 
    x == y
  })
 
  property("isDefined") = forAll ((o: Optional[Int]) =>
    (o.isDefined) == (o.toOption.isDefined))
 
  property("isEmpty") = forAll ((o: Optional[Int]) =>
    o.isEmpty == o.toOption.isEmpty)
 
  property("orElse") = forAll ((o: Optional[Int], p: Optional[Int]) =>
    (o orElse p).toOption == (o.toOption orElse p.toOption))
 
  property("toLeft") = forAll ((o: Optional[Int], n: Int) =>
    (o toLeft n) == (o.toOption toLeft n))
 
  property("toRight") = forAll ((o: Optional[Int], n: Int) =>
    (o toRight n) == (o.toOption toRight n))
 
  property("toList") = forAll ((o: Optional[Int]) =>
    o.toList == o.toOption.toList)
 
  property("iterator") = forAll ((o: Optional[Int]) =>
    o.iterator sameElements o.toOption.iterator)
 
  // *** READ THIS COMMENT FIRST ***
  // Note that scala.Option has no such equivalent to this method
  // Therefore, reading this test may give away clues to how it might be solved.
  // If you do not wish to spoil it, look away now and follow the
  // instruction in the Exercise comment.
  property("applic") = forAll ((o: Optional[Int => String], p: Optional[Int]) =>
    (p applic o).toOption ==
    (for(f <- o.toOption;
         n <- p.toOption)
    yield f(n)))
 
  def trace[A](a: A) = {
    println(a)
    a
  }
 
  property("mapOptionals") = forAll((f: Int => Optional[String], o: List[Int]) =>
  {
    val i = o map f
    mapOptionals(f, o) == (if(i forall (_.isDefined)) some(i map (_.get)) else none)
  })
 
  property("sequenceOptionals") = forAll((o: List[Optional[String]]) =>
      sequenceOptionals(o) == (if(o exists (_.isEmpty)) none else some(o map (_.get))))
 
  property("mapOptionalsAgain") = forAll((f: Int => Optional[String], o: List[Int]) =>
      mapOptionalsAgain(f, o) == mapOptionals(f, o))
 
  property("sequenceOptionalsAgain") = forAll((o: List[Optional[String]]) =>
      sequenceOptionalsAgain(o) == sequenceOptionals(o))
 
  property("joinOptionals") = forAll((o: Optional[Optional[String]]) =>
      joinOptionals(o) == (if(o.isDefined && o.get.isDefined) o.get else none))
 
  property("filterOptionals") = forAll((f: Int => Optional[Boolean], o: List[Int]) =>
      filterOptionals(f, o) == (if(o exists (f(_).isEmpty)) none else some(o filter (f(_).get))))
 
  property("fillOptionals") = forAll((n: Int, o: Optional[String]) =>
      (n < 1000) ==> // prevent stack consumption
      (fillOptionals(n, o) == (if(n <= 0) some(Nil) else (o map (List.fill(n)(_))))))
 
  property("fillOptionalsAgain") = forAll((n: Int, o: Optional[String]) =>
      (n < 1000) ==> // prevent stack consumption      
      (fillOptionalsAgain(n, o) == fillOptionals(n, o)))
 
  property("mapOptionalsYetAgain") = forAll((f: Int => Optional[String], o: List[Int]) =>
      mapOptionalsYetAgain(f, o) == mapOptionals(f, o))
 
  property("mapWhatever") = forAll((f: Int => Optional[String], o: List[Int]) =>
      mapWhatever(f, o) == mapOptionals(f, o))
 
  /*
  $ scala -classpath .:scalacheck_2.8.0-1.7.jar TestOptional
  + Optional.map: OK, passed 100 tests.                                         
  + Optional.get: OK, passed 100 tests.                                         
  + Optional.flatMap: OK, passed 100 tests.                                     
  + Optional.mapAgain: OK, passed 100 tests.                                    
  + Optional.getOrElse: OK, passed 100 tests.                                   
  + Optional.filter: OK, passed 100 tests.                                      
  + Optional.exists: OK, passed 100 tests.                                      
  + Optional.forall: OK, passed 100 tests.                                      
  + Optional.foreach: OK, passed 100 tests.                                     
  + Optional.isDefined: OK, passed 100 tests.                                   
  + Optional.isEmpty: OK, passed 100 tests.                                     
  + Optional.orElse: OK, passed 100 tests.                                      
  + Optional.toLeft: OK, passed 100 tests.                                      
  + Optional.toRight: OK, passed 100 tests.                                     
  + Optional.toList: OK, passed 100 tests.                                      
  + Optional.iterator: OK, passed 100 tests.                                    
  + Optional.applic: OK, passed 100 tests.                                      
  + Optional.mapOptionals: OK, passed 100 tests.                                
  + Optional.sequenceOptionals: OK, passed 100 tests.                           
  + Optional.mapOptionalsAgain: OK, passed 100 tests.                           
  + Optional.sequenceOptionalsAgain: OK, passed 100 tests.                      
  + Optional.joinOptionals: OK, passed 100 tests.                               
  + Optional.filterOptionals: OK, passed 100 tests.                             
  + Optional.fillOptionals: OK, passed 100 tests.                          
  + Optional.fillOptionalsAgain: OK, passed 100 tests.                     
  + Optional.mapOptionalsYetAgain: OK, passed 100 tests.                        
  + Optional.mapWhatever: OK, passed 100 tests.          
  */  
}

// Scala version 2.8.0.final
// http://scalacheck.googlecode.com/files/scalacheck_2.8.0-1.8-SNAPSHOT.jar
 
 
/*
 
  Below are 15 exercises. The task is to emulate the scala.Option API
  without using Some/None subtypes, but instead using a fold (called a
  catamorphism).
 
  A couple of functions are already done (map, get)
  to be used as an example. ScalaCheck tests are given below to
  verify the work. The desired result is to have all tests passing.
 
  The 15th exercise is not available in the existing Scala API so
  instructions are given in the comments.
 
  Revision History
  ================
 
  23/08/2010
  Initial revision
 
  ----------------
 
  23/08/2010
  Fixed prop_getOrElse. Thanks Michael Bayne.
 
  ----------------
 
  26/08/2010
  Add lazy annotation to orElse method.
 
*/
 
 
trait Optional[A] {
  // single abstract method
  def fold[X](some: A => X, none: => X): X
 
  import Optional._
 
  // Done for you.
  def map[B](f: A => B): Optional[B] =
    fold(f andThen some, none[B])
 
  // Done for you.
  // WARNING: undefined for None
  def get: A =
    fold(a => a, error("None.get"))
 
  // Exercise 1
  def flatMap[B](f: A => Optional[B]): Optional[B] =
    error("todo")
 
  // Exercise 2
  // Rewrite map but use flatMap, not fold.
  def mapAgain[B](f: A => B): Optional[B] =
    error("todo")
 
  // Exercise 3
  def getOrElse(e: => A): A =
    error("todo")
 
  // Exercise 4
  def filter(p: A => Boolean): Optional[A] =
    error("todo")
 
  // Exercise 5
  def exists(p: A => Boolean): Boolean =
    error("todo")
 
  // Exercise 6
  def forall(p: A => Boolean): Boolean =
    error("todo")
 
  // Exercise 7
  def foreach(f: A => Unit): Unit =
    error("todo")
 
  // Exercise 8
  def isDefined: Boolean =
    error("todo")
 
  // Exercise 9
  def isEmpty: Boolean =
    error("todo")
 
  // Exercise 10
  def orElse(o: => Optional[A]): Optional[A] =
    error("todo")
 
  // Exercise 11
  def toLeft[X](right: => X): Either[A, X] =
    error("todo")
 
  // Exercise 12
  def toRight[X](left: => X): Either[X, A] =
    error("todo")
 
  // Exercise 13
  def toList: List[A] =
    error("todo")
 
  // Exercise 14
  def iterator: Iterator[A] =
    error("todo")
 
  // Exercise 15 The Clincher!
  // Return a none value if either this or the argument is none.
  // Otherwise apply the function to the argument in some.
  // Don't be afraid to use functions you have written.
  // Better style, more points!
  def applic[B](f: Optional[A => B]): Optional[B] =
    error("todo")
 
  // Utility
  def toOption: Option[A] = fold(Some(_), None)
}
 
object Optional {
  // Done for you
  def none[A]: Optional[A] = new Optional[A] {
    def fold[X](some: A => X, none: => X) = none
  }
 
  // Done for you
  def some[A](a: A): Optional[A] = new Optional[A] {
    def fold[X](some: A => X, none: => X) = some(a)
  }
 
  // Utility
  def fromOption[A](o: Option[A]): Optional[A] = o match {
    case None    => none
    case Some(a) => some(a)
  }
}
 
import org.scalacheck._
import Arbitrary.arbitrary
import Prop._
 
object TestOptional {
  import Optional._
 
  implicit def ArbitraryOptional[A](implicit a: Arbitrary[A]): Arbitrary[Optional[A]] =
    Arbitrary(arbitrary[Option[A]] map fromOption)
 
  val prop_map = forAll ((o: Optional[Int], f: Int => String) =>
    (o map f).toOption == (o.toOption map f))
 
  val prop_get = forAll((o: Optional[Int]) =>
    o.isDefined ==>
      (o.get == o.toOption.get))
 
  val prop_flatMap = forAll((o: Optional[Int], f: Int => Optional[String]) =>
    (o flatMap f).toOption == (o.toOption flatMap (f(_).toOption)))
 
  val prop_mapAgain = forAll ((o: Optional[Int], f: Int => String) =>
    (o mapAgain f).toOption == (o map f).toOption)
 
  val prop_getOrElse = forAll ((o: Optional[Int], n: Int) =>
    (o getOrElse n) == (o.toOption getOrElse n))
 
  val prop_filter = forAll ((o: Optional[Int], f: Int => Boolean) =>
    (o filter f).toOption == (o.toOption filter f))
 
  val prop_exists = forAll ((o: Optional[Int], f: Int => Boolean) =>
    (o exists f) == (o.toOption exists f))
 
  val prop_forall = forAll ((o: Optional[Int], f: Int => Boolean) =>
    (o forall f) == (o.toOption forall f))
 
  val prop_foreach = forAll ((o: Optional[Int], f: Int => Unit, n: Int) => {
    var x: Int = n
    var y: Int = x
 
    o foreach (t => x = x + t)
    o.toOption foreach (t => y = y + t)
 
    x == y
  })
 
  val prop_isDefined = forAll ((o: Optional[Int]) =>
    (o.isDefined) == (o.toOption.isDefined))
 
  val prop_isEmpty = forAll ((o: Optional[Int]) =>
    o.isEmpty == o.toOption.isEmpty)
 
  val prop_orElse = forAll ((o: Optional[Int], p: Optional[Int]) =>
    (o orElse p).toOption == (o.toOption orElse p.toOption))
 
  val prop_toLeft = forAll ((o: Optional[Int], n: Int) =>
    (o toLeft n) == (o.toOption toLeft n))
 
  val prop_toRight = forAll ((o: Optional[Int], n: Int) =>
    (o toRight n) == (o.toOption toRight n))
 
  val prop_toList = forAll ((o: Optional[Int]) =>
    o.toList == o.toOption.toList)
 
  val prop_iterator = forAll ((o: Optional[Int]) =>
    o.iterator sameElements o.toOption.iterator)
 
  // *** READ THIS COMMENT FIRST ***
  // Note that scala.Option has no such equivalent to this method
  // Therefore, reading this test may give away clues to how it might be solved.
  // If you do not wish to spoil it, look away now and follow the 
  // instruction in the Exercise comment.
  val prop_applic = forAll ((o: Optional[Int => String], p: Optional[Int]) =>
    (p applic o).toOption ==
    (for(f <- o.toOption;
        n <- p.toOption)
    yield f(n)))
 
  val props =
    List(
      prop_map,
      prop_get,
      prop_flatMap,
      prop_mapAgain,
      prop_getOrElse,
      prop_filter,
      prop_exists,
      prop_forall,
      prop_foreach,
      prop_isDefined,
      prop_isEmpty,
      prop_orElse,
      prop_toLeft,
      prop_toRight,
      prop_toList,
      prop_iterator,
      prop_applic
    )
 
  /*
  $ scala -classpath .:scalacheck_2.8.0-1.8-SNAPSHOT.jar TestOptional
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                                                       
  + OK, passed 100 tests.                       
  */
  def main(args: Array[String]) {
    props foreach (_.check)
  }
}

// A typical data type with a single abstract method
case class Inter[A](f: Int => A) {
  // which is a functor
  def map[B](g: A => B): Inter[B] =
    Inter(n => g(f(n)))
 
  // and a monad (see unital below)
  def flatMap[B](g: A => Inter[B]): Inter[B] = 
    Inter(n => g(f(n)).f(n))
}
 
// unital: A => F[A]
// Implementations for F=Option and F=Inter
object Unitals {
  def unitalOption[A](a: A): Option[A] =
    Some(a)
 
  def unitalInter[A](a: A): Inter[A] =
    Inter(_ => a)
}
 
// Exercises
// 
// It is recommended to use only map, flatMap and unital* for
// Option or Inter when implementing the exercises below.
// Any other libraries are acceptable (e.g. List functions).
object Sequencing {
  import Unitals._
 
  // Exercise 1 of 3
  // ===============
  // Implement a function that returns None if the given list
  // contains any None values, otherwise, all the Some values.
  def sequenceOption[A](x: List[Option[A]]): Option[List[A]] =     
    error("todo")
 
    // SOLUTIONx2 (ROT-13)
    /*
    1)
    k.sbyqEvtug(havgnyBcgvba(Avy: Yvfg[N]))((n, o) => n syngZnc (k => o znc (k :: _)))
 
    2)
    k zngpu {
      pnfr Avy  => havgnyBcgvba(Avy)
      pnfr u::g => u syngZnc (k => frdhraprBcgvba(g) znc (k :: _))
    }
    */
 
  // Exercise 2 of 3
  // ===============
  // Implement a function that returns an Inter that applies an Int
  // to all the Inter implementations in the List of Inters and returns
  // all the results.
  def sequenceInter[A](x: List[Inter[A]]): Inter[List[A]] =     
    error("todo")
 
    // SOLUTIONx2 (ROT-13)
    /*
    1)
    k.sbyqEvtug(havgnyVagre(Avy: Yvfg[N]))((n, o) => n syngZnc (k => o znc (k :: _)))
 
    2)
    k zngpu {
      pnfr Avy  => havgnyVagre(Avy)
      pnfr u::g => u syngZnc (k => frdhraprVagre(g) znc (k :: _))
    }
    */
 
  // Exercise 3 of 3
  // ===============
  // There is repetition in the above exercises.
  // How might we be rid of it?
  // That is for Part 2.
 
  def main(args: Array[String]) {
    def assertEquals[A](a1: A, a2: A) {
      if(a1 != a2)
        error("Assertion error. Expected: " + a1 + " Actual: " + a2)
    }
 
    def assertInterEquals[A](a1: Inter[A], a2: Inter[A]) {
      val testInts = List(1, 2, 0, -7, -9, 113, -2048)
      assertEquals(testInts.map(a1.f(_)), testInts.map(a2.f(_)))
    }
 
    // sequenceOption
    assertEquals(sequenceOption(List(Some(7),
        Some(8), Some(9))), Some(List(7, 8, 9)))
    assertEquals(sequenceOption(List(Some(7), None, Some(9))),
        None)
    assertEquals(sequenceOption(List()),
      Some(List()))
 
    // sequenceInter
    assertInterEquals(sequenceInter(List()),
      Inter(_ => List()))
    assertInterEquals(sequenceInter(List(Inter(1+),
        Inter(2*))), Inter(n => List(1+n, 2*n)))    
  } 
}

data Optional a = Full a | Empty deriving (Eq, Show)

Optional a -> a -> a

type Optional a = forall x. (a -> x) -> x -> x

let cata :: (a -> x) -> x -> x
cata Full Empty == id

forall a x. ((a -> x) -> x -> x) -> a)

interface Function<A, B> {
  B apply(A a);
}
 
class C {
  static <A, B, C> Function<A, C> c(final Function<A, B> f,
                                    final Function<B, C> g) {
      .... todo
  }
}

// A list that is either empty or has one element.
public abstract class NoneOrOne<A> {
  // The key abstract method (catamorphism).
  public abstract <X> X fold(Thunk<X> none, Func<A, X> one);
 
  // Produces an empty list.
  public static <A> NoneOrOne<A> none() {
    throw new Error("todo");
  }
 
  // Produces a list with the given element.
  public static <A> NoneOrOne<A> one(final A a) {
    throw new Error("todo");
  }
 
  // Returns true if this list is empty.
  public boolean isEmpty() {
    throw new Error("todo");
  }
 
  // Maps the given function on each element of this list.
  public <B> NoneOrOne<B> map(final Func<A, B> f) {
    throw new Error("todo");
  }
 
  // Filters the list on the given predicate.
  // The element is retained if the predicate satisfies.
  public NoneOrOne<A> filter(final Func<A, Boolean> p) {
    throw new Error("todo");
  }
 
  // Applies the possible function on this list.
  public <B> NoneOrOne<B> app(final NoneOrOne<Func<A, B>> f) {
    throw new Error("todo");
  }
 
  // Binds the given function on this list.
  public <B> NoneOrOne<B> bind(final Func<A, NoneOrOne<B>> f) {
    throw new Error("todo");
  }
 
  // Returns the value held in this list.
  // However, if it is empty, return the given default value.
  public A get(final Thunk<A> def) {
    throw new Error("todo");
  }
 
  // If this list is empty, return the given one.
  // Otherwise, return this list.
  public NoneOrOne<A> orElse(final NoneOrOne<A> els) {
    throw new Error("todo");
  }
 
  // For debugging
  public String toString() {
    final StringBuilder s = new StringBuilder();
    s.append('[');
    fold(new Thunk<Object>() {
      public Object value() {
        return null; // Java has no suitable unit type.
      }
    }, new Func<A, Object>() {
      public Object apply(final A a) {
        s.append(a);
        return null; // Java has no suitable unit type.
      }
    });
    return s.append(']').toString();
  }
 
  // TEST
  public static void main(final String[] args) {
    final NoneOrOne<Integer> s = NoneOrOne.one(Integer.parseInt(args[0]));
 
    final NoneOrOne<String> t = s.map(new Func<Integer, String>() {
      public String apply(final Integer i) {
        return new StringBuilder(Integer.valueOf(i * 123).toString()).reverse().toString();
      }
    });
 
    final NoneOrOne<Integer> u = s.filter(new Func<Integer, Boolean>() {
      public Boolean apply(final Integer i) {
        return i < 100;
      }
    });
 
    final NoneOrOne<String> v = s.app(NoneOrOne.<Func<Integer, String>>one(
      new Func<Integer, String>() {
      public String apply(final Integer i) {
        return String.valueOf(Math.pow(i, i));
      }
    }));
 
    final NoneOrOne<String> w = s.bind(new Func<Integer, NoneOrOne<String>>() {
      public NoneOrOne<String> apply(final Integer i) {
        return i % 2 == 0 ?
          one("it's even") :
          i % 3 == 0 ?
            one("it's divisible by 3 but not 6") :
            NoneOrOne.<String>none();
      }
    });
 
    final Integer x = s.get(new Thunk<Integer>() {
      public Integer value() {
        return 42;
      }
    });
 
    final NoneOrOne<Integer> y = NoneOrOne.<Integer>none().orElse(s);
 
    /*
    $ java NoneOrOne 122
    [122]
    [60051]
    []
    [3.4347832971354663E254]
    [it's even]
    122
    [122]
 
    $ java -classpath /tmp/ NoneOrOne 12
    [12]
    [6741]
    [12]
    [8.916100448256E12]
    [it's even]
    12
    [12]
    */
    System.out.println(s);
    System.out.println(t);
    System.out.println(u);
    System.out.println(v);
    System.out.println(w);
    System.out.println(x);
    System.out.println(y);
  }
}
 
// Laziness
interface Thunk<T> {
  T value();
}
 
// Takes an A and produces a B
interface Func<A, B> {
  B apply(A a);
}