Skip to content

Instantly share code, notes, and snippets.

@davidandrzej
davidandrzej / grasshopper.m
Created Mar 1, 2017
Code for "Improving Diversity in Ranking using Absorbing Random Walks" (NAACL HLT 2007)
View grasshopper.m
function [l v] = grasshopper(W, r, lambda, k)
%
% Reranking items by random walk on graph with absorbing states.
% (CREDIT: Jerry Zhu jerryzhu@cs.wisc.edu)
%
% INPUT
%
% W: n*n weight matrix with non-negative entries.
% W(i,j) = edge weight for the edge i->j
% The graph can be directed or undirected. Self-edges are allowed.
View keybase.md

Keybase proof

I hereby claim:

  • I am davidandrzej on github.
  • I am davidandrzej (https://keybase.io/davidandrzej) on keybase.
  • I have a public key whose fingerprint is 5203 3009 B157 505D DF21 9C16 B86B BB05 D29E 1BFE

To claim this, I am signing this object:

View lawblog-mapmonoid.scala
scala> implicit val em = EvaluationMonoid
em: EvaluationMonoid.type = EvaluationMonoid$@34f5b235
scala> implicit val mm = mapMonoid[String,Evaluation]
mm: scalaz.Monoid[Map[String,Evaluation]] = scalaz.std.MapInstances$$anon$4@13105b09
scala> val dataset1 = Map("modelA" -> Evaluation(3,2),
| "modelB" -> Evaluation(4,1))
dataset1: scala.collection.immutable.Map[String,Evaluation] =
Map(modelA -> Evaluation(3,2), modelB -> Evaluation(4,1))
View lawblog-proptest.scala
val evalGen = for {total <- Gen.choose(0, 1000);
correct <- Gen.choose(0, total)}
yield Evaluation(total,correct)
"Evaluation Monoid" should {
import EvaluationMonoid._
implicit val eq = Equal.equalA[Evaluation]
"obey Monoid typeclass Law" in {
View lawblog-spottest.scala
"Evaluation Monoid" should {
import EvaluationMonoid._
implicit val eq = Equal.equalA[Evaluation]
val testEvaluation = Evaluation(3, 2)
"obey Monoid typeclass Law" in {
Monoid.monoidLaw.leftIdentity(testEval) should be (true)
Monoid.monoidLaw.rightIdentity(testEval) should be (true)
}
View lawblog-evalmonoid.scala
object EvaluationMonoid extends Monoid[Evaluation] {
def zero = Evaluation(0,0)
def append(x: Evaluation, y: => Evaluation) =
Evaluation(x.total + y.total, x.correct + y.correct)
}
View lawblog-evaluationscala
case class Evaluation(total: Int, correct: Int)
View lawblog-monoidlaw.scala
trait Monoid[F] extends Semigroup[F] {
...
trait MonoidLaw extends SemigroupLaw {
def leftIdentity(a: F)(implicit F: Equal[F]) =
F.equal(a, append(zero, a))
def rightIdentity(a: F)(implicit F: Equal[F]) =
F.equal(a, append(a, zero))
}
...
}
View lawblog-additup.scala
def addItUp[F : Monoid](items: Seq[F]): F = {
// Combine a bunch of items
val m = implicitly[Monoid[F]]
items.foldLeft(m.zero){case (total, next) => m.append(total,next)}
}
scala> addItUp(Seq("day ", "after ", "day"))
res1: String = "day after day"
scala> addItUp(Seq(1,2,3))
res2: Int = 6
View lawblog-monoid.scala
trait Monoid[F] {
def zero: F
def append(f1: F, f2: => F): F
}