commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Matthew Pocock <turingatemyhams...@gmail.com>
Subject Re: [Graph] On graph weight type(s)
Date Thu, 15 Dec 2011 12:37:40 GMT
Hi,

On 15 December 2011 11:35, James Carman <james@carmanconsulting.com> wrote:


> public interface BinaryOperation<T>
> {
>  public T execute(T operand1, T operand2);
> }
>
> Perhaps we can come up with an interface that combines the two
> aspects.  I'm trying to think of mathematically what that would be
> called.  By the way, what do you need to know "HasZero"?  A sum
> operation has to have a "zero", doesn't it?


The mathematical hierarchy goes: semigroup -> monoid.

http://en.wikipedia.org/wiki/Semigroup
http://en.wikipedia.org/wiki/Monoid

You don't need a full group here as you are only interested in a single
operation, not a pair of interacting operations. There are several
JVM-hosted libraries that model this hierarchy to a greater or lesser
degree. scalaz uses:

trait Semigroup[S] {
  def append(s1: S
<http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#22357>,
s2: => S): S <http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#22357>
}

trait Zero[Z] {
  val zero: Z <http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#22160>
}

trait Monoid[M] extends Zero
<http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#17945>[M]
with Semigroup <http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#15476>[M]

http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html
http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html
http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Monoid.scala.html

If you're not used to reading scala, here's the essentially equivalent
definitions in Java:

public interface Semigroup<S> {
  public S append(S s1, S s2);
}

public interface Zero<Z> {

  public Z zero();
}

public interface Monoid<M> extends
Zero<http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#17945><M>,
Semigroup<http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#15476>
<M>


So, given that you have Ordering<O> already (or is that Comparator<C>?),
I'd say that Weight is defined as:

// insert comments here about the consistency of append and compare
public interface Weight<W> extends Monoid<W>, Ordered<W>

Of course, a sensible default implementation of Weight would delegate to
Monoid and Ordered instances and you can then pray to the gods of hotspot
to inline this all away.

public <W> Weight<W> weight(Monoid<W> m, Ordered<W> o) {
  new Weight<W>() {
    public W zero() { return m.zero(); }
    ...
  }
}

Matthew

-- 
Dr Matthew Pocock
Integrative Bioinformatics Group, School of Computing Science, Newcastle
University
mailto: turingatemyhamster@gmail.com
gchat: turingatemyhamster@gmail.com
msn: matthew_pocock@yahoo.co.uk
irc.freenode.net: drdozer
skype: matthew.pocock
tel: (0191) 2566550
mob: +447535664143

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message