noodling towards a functional brain

Tuesday, December 08, 2009

A monadic Visitor

This Reader-esque monad emerged from my code this morning:
trait A {
  def accept[T](v: V[T]): T
}

class B(val s: String) extends A {
  var i = 0
  override def accept[T](v: V[T]): T = v.visit(this)
}

class C(val s: String) extends A {
  var i = 0
  override def accept[T](v: V[T]): T = v.visit(this)
}

class D(val s: String) extends A {
  var i = 0
  override def accept[T](v: V[T]): T = v.visit(this)
}

trait V[T] {
  outer =>
  def visit(b: B): T
  def visit(c: C): T
  def visit(d: D): T

  def map[U](f: T => U): V[U] = new V[U] {
    def visit(b: B): U = f(outer.visit(b))
    def visit(c: C): U = f(outer.visit(c))
    def visit(d: D): U = f(outer.visit(d))
  }

  def flatMap[U](f: T => V[U]): V[U]= new V[U] {
    def visit(b: B): U = f(outer.visit(b)).visit(b)
    def visit(c: C): U = f(outer.visit(c)).visit(c)
    def visit(d: D): U = f(outer.visit(d)).visit(d)
  }
}

object V {
  def pure[T](t: T): V[T] = new V[T] {
    def visit(b: B) = t
    def visit(c: C) = t
    def visit(d: D) = t
  }
}
And the test:
object Test {
  def main(argv: Array[String]) {
    class VI(i: Int) extends V[Int] {
      def visit(b: B) = error("not supported")

      def visit(c: C) = {
        println("vi: " + c.s + " = " + c.i)
        c.i = c.i + i
        c.i
      }

      def visit(d: D) = {
        println("vi: " + d.s + " = " + d.i)
        d.i = d.i + i
        d.i
      }
    }

    def f(i: Int): V[Int] = {
      println("f: " + i)
      new VI(i)
    }

    def g(i: Int): V[Int] = {
      println("g: " + i)
      new VI(i)
    }

    val c1: A = new C("c1")
    val c2: A = new C("c2")
    val d1: A = new D("d1")
    val v = new VI(1)
    println(c1.accept(v.flatMap(f).flatMap(g)))
    println(c2.accept(v.flatMap(x => f(x).flatMap(g))))
    println(d1.accept(v.flatMap(f).flatMap(g).flatMap(f).flatMap(g)))
  }
}
As far as I can tell, this satisfies the monad laws. Am I missing anything? If not, this is the first monad I've "found in the wild!"

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)
  }
}

About Me

My photo
aspiring to elegant simplicity