Ehm, a monad perhaps?

Disclosure: I know nothing about monads, or category theory in general, to an amazingly good approximation. I apologise in advance for any botched terminology or shoddy thinking.

Also, this kind of thing is a wonderful antidote to days staring at C++. Really. That's why I'm blogging about it, even though progress is pitifully slow.

Anyway, continuing with the code in previous entries, I ended up with these little methods (with minor implementation details in the Empty object to produce errors/None/Nil, resp.):

def apply[B]( w: Var[B] ) : B = w match {
  case _ : v.type => x
  case _ => Env.this.apply(w)
}
def get[B]( w: Var[B] ) : Option[B] = w match {
  case _ : v.type => Some(x)
  case _ => Env.this.get(w)
}
def history[B]( w: Var[B] ) : List[B] = w match {
  case _ : v.type => x :: Env.this.history(w)
  case _ => Env.this.history(w)
}

They fetch a variable, fetch an optional variable, and get a list of all the values of a variable. They look pretty similar to me. Something niggled at the back of my head, especially combined with the code in Empty which was essentially spitting out _|_ or some zero-like object.

Hey, aren't lists and options (Maybes)... monads? And don't some monads have a sort of addition and zero? Given those, can't I cut out that irritating repetition from my example?

Well, the first few attempts failed to compile, so I threw syntax at it until:

def fetch[A,B]( v: Var[A], unit: A => B, mplus: (B, () => B) => B, mzero: () => B ) : B

def apply[A]( v: Var[A] ) : A = 
  fetch( v, (x:A) => x, (x:A, _: ()=>A) => x, () => error("var not found: "+v) )

def get[A]( v: Var[A] ) : Option[A] = 
  fetch( v, (x:A) => Some(x),  (x:Option[A], _: ()=>Option[A]) => x, () => None )

def history[A]( v: Var[A] ) : List[A] = 
  fetch( v, (x:A) => x :: Nil, (x:List[A], y: ()=>List[A]) => x ::: y(), () => Nil )

Well, that seems to compile, even if its ugly. The implementation inside Env and Empty now looks like this:

//Env
def fetch[A,B]( w: Var[A], unit: A => B, mplus: (B,()=>B) => B, mzero: () => B ) : B = w match {
  case _ : v.type => mplus( unit( x ), () => Env.this.fetch[A,B](w,unit,mplus,mzero) )
  case _ => Env.this.fetch(w,unit,mplus,mzero)
}

//Empty - easy!
def fetch[A,B]( v: Var[A], unit: A => B, mplus: (B,() => B) => B, mzero: () => B ) : B = mzero()

So, the mighty feat of transforming three simple four-line functions into three one-liners! Er, and a four-line definition, plus an extra declaration. Score one for abstraction, or something.

I'd like the syntax to be nicer, though, and I'm pretty sure I don't like the use of ::: (that's the list concatenation operator in Scala, for reference). Eh, anyway, I thought it was neat enough to be interesting, and it extends nicely. Adding a version of apply with a default value is very nice, for example; mzero just returns the default, and the inclusion of the default value means the type parameter is inferred.