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!"

3 comments:

  1. This is amazingly beautiful. Thanks a lot!

    ReplyDelete
  2. 4 years late, but isn't this exactly the free monad over the F-algebra exposed by your visitor?

    ReplyDelete
  3. 9 years later, rereading; seems like I want to add this to my book!

    ReplyDelete

Note: Only a member of this blog may post a comment.

About Me

My photo
aspiring to elegant simplicity