noodling towards a functional brain

Wednesday, December 02, 2009

So much from so little

My solution to Tony's catamorphism challenge:
trait MyOption[+A] {
  import MyOption._

  def cata[X](some: A => X, none: => X): X
  def map[B](f: A => B): MyOption[B] = cata(a => some(f(a)), none[B])
  def flatMap[B](f: A => MyOption[B]): MyOption[B] = cata(f, none[B])
  def getOrElse[AA >: A](e: => AA): AA = cata(a => a, e)
  def filter(p: A => Boolean): MyOption[A] = if (cata(p, false)) cata(a => some(a), none[A]) else none[A]
  def foreach(f: A => Unit): Unit = cata(f, ())
  def isDefined: Boolean = cata(_ => true, false)
  def isEmpty: Boolean = cata(_ => false, true)
  def get: A = cata(a => a, error("get on none"))
  def orElse[AA >: A](o: MyOption[AA]): MyOption[AA] = cata(a => some(a), o)
  def toLeft[X](right: => X): Either[A, X] = cata(a => Left(a), Right(right))
  def toRight[X](left: => X): Either[X, A] = cata(a => Right(a), Left(left))
  def toList: List[A] = cata(a => List(a), Nil)
  def iterator: Iterator[A] = toList.elements
}

object MyOption {
  def none[A] = new MyOption[A] {
    def cata[X](s: A => X, n: => X) = n
  }

  def some[A](a: A) = new MyOption[A] {
    def cata[X](s: A => X, n: => X) = s(a)
  }
}

6 comments:

  1. There were some differences between your version and mine. In particular, using some or none (or MyOption.some/MyOption.none, which I tried first) doesn't work for me. The compiler complains that there is a type mismatch ("Object with MyOption" for MyOption). The way I solved it was to create new MyOption objects at the places where none/some were needed, but your solution is of course more elegant. Do you have any idea what might be causing this discrepancy? (I use 2.8.0.r18678)

    ReplyDelete
  2. Peter: the "import MyOption._" is necessary for the none and some functions to be in scope if you don't fully qualify them, but I'm not certain why the fully qualified names wouldn't work. It sounds like it'd most likely be a type inference issue, which you can fix by explicitly specifying the return type of some and none. My solution used scala 2.7.7.

    ReplyDelete
  3. I found it: your code gets errors when loaded into the REPL, but works fine when compiled with scalac.

    Your iterator method is going to break in 2.8, btw.

    ReplyDelete
  4. Your filter works OK for the MyOption type, but it doesn't have the same form as the others -- try putting the if inside of the cata. This might be stealing Tony's thunder, but you'll need to do that if you want to generalize to MyList (where the abstract method is def cata[X](cons: (A, X) => X, nil: => X): X).

    ReplyDelete
  5. @Brian

    I implemented filter as

    def filter (p: A => Boolean) =
    cata(a => if (p(a)) this else none, this)

    which I believe satisfies this.

    (http://pelewin.blogspot.com/2009/12/catamorphism-exercise-by-tony-morris.html)

    ReplyDelete
  6. Brian & Peter: very nice - I actually almost did that (the repeated none irked me) but didn't quite get it and went back to the easy way. Peter, I like the use of this in your implementation - I should have attempted to use this more.

    ReplyDelete

About Me

My Photo
aspiring to elegant simplicity