Skip to content

Instantly share code, notes, and snippets.

View krishnanraman's full-sized avatar

Krishnan Raman krishnanraman

44 followers · 26 following
View GitHub Profile
@johnynek
johnynek / gist:8961994
Last active August 29, 2015 13:56
Some Questions with Sketch Monoids

Unifying Sketch Monoids

As I discussed in Algebra for Analytics, many sketch monoids, such as Bloom filters, HyperLogLog, and Count-min sketch, can be described as a hashing (projection) of items into a sparse space, then using two different commutative monoids to read and write respectively. Finally, the read monoids always have the property that (a + b) <= a, b and the write monoids has the property that (a + b) >= a, b.

##Some questions:

  1. Note how similar CMS and Bloom filters are. The difference: bloom hashes k times onto the same space, CMS hashes k times onto a k orthogonal subspaces. Why the difference? Imagine a fixed space bloom that hashes onto k orthogonal spaces, or an overlapping CMS that hashes onto k * m length space. How do the error asymptotics change?
  2. CMS has many query modes (dot product, etc...) can those generalize to other sketchs (HLL, Bloom)?
  3. What other sketch or non-sketch algorithms can be expressed in this dual mo
@danclien
danclien / catamorphism_identity_example.scala
Last active August 29, 2015 13:56
List(1,2,3,4,5).foldRight(List.empty[Int])(_ :: _)
//res1: List[Int] = List(1, 2, 3, 4, 5)
/*
Passing in the type constructors for an abstract data type to its fold method
is the identity function.
List is made up of `Nil` and `Cons` objects.
*/
@danclien
danclien / scalaz_console_io_free_monad.scala
Last active August 29, 2015 13:57
Attempt to write a monad for console IO using scalaz's Free monad
:paste
import scalaz._, Scalaz._, scalaz.Free.{Suspend, Return}
// Console grammar
sealed trait ConsoleF[+A]
object Console {
case class WriteLine[A](msg: String, o: A) extends ConsoleF[A]
case class ReadLine[A](o: String => A) extends ConsoleF[A]
}
@tonymorris
tonymorris / haskell-scala.html
Created June 4, 2014 02:07
http://programmers.stackexchange.com/questions/51245/what-kind-of-things-are-easy-in-haskell-and-hard-in-scala-and-vice-versa has been deleted
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en-US">
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8"/>
<link rel="stylesheet" href="/stylesheets/export.css"/>
<link rel="shortcut icon" type="image/x-icon" href="/favicon.ico"/>
<link rel="canonical" href="http://www.stackprinter.com/export?service=programmers.stackexchange&amp;question=51245&amp;printer=false&amp;linktohome=true"/>
<title>What kind of things are easy in Haskell and hard in Scala, and vice versa?</title>
<script type="text/javascript" src="/javascripts/jquery-1.4.2.min.js"></script>
<script type="text/javascript" src="/javascripts/main.js"></script>
@seanjtaylor
seanjtaylor / weather_data.R
Created January 24, 2015 17:16
library(mgcv)
library(ggplot2)
library(dplyr)
library(XML)
library(weatherData)
us.airports.url <- 'http://www.world-airport-codes.com/us-top-40-airports.html'
us.airports <- readHTMLTable(us.airports.url)[[1]] %>%
filter(!is.na(IATA)) %>%
@gclaramunt
gclaramunt / Ids.scala
Created September 9, 2012 03:05
Tagged Ids using Phantom types
trait Entity
trait User extends Entity
trait Product extends Entity
case class Id[T<:Entity](id:String)
def buy(pId:Id[Product],uId:Id[User])="Bought product %s for user %s".format(pId.id,uId.id)
val pId=new Id[Product]("1")
@tonymorris
tonymorris / FList.scala
Last active December 10, 2015 02:18
foldMap is equivalent to scala.List
trait Semigroup[A] {
def op(a1: A, a2: A): A
}
trait Monoid[A] extends Semigroup[A] {
def id: A
}
object Monoid {
implicit def ListMonoid[A]: Monoid[List[A]] =
@johnynek
johnynek / heterfn.scala
Created June 18, 2013 04:29
An example showing how to make a function that takes one of many input types.
// Taken from: http://jnordenberg.blogspot.com/2008/08/hlist-in-scala.html
object HListTest {
sealed trait HList
final class HNil extends HList {
def ::[T](v : T) = HCons(v, this)
}
val HNil = new HNil()
@johnynek
johnynek / WriteOnce
Created July 16, 2013 14:20
class WriteOnce[T] {
private val ref = new java.util.concurrent.atomic.AtomicReference[Option[T]](None)
def init(t: T) { if(!ref.compareAndSet(None, Some(t))) sys.error("Already written"); }
def get: Option[T] = ref.get
}
scala> val w = new WriteOnce[Int]
w: WriteOnce[Int] = WriteOnce@215d55cb
scala> w.get
@johnynek
johnynek / WeakRefMonad.scala
Created December 10, 2013 23:53
Weak Reference is a monad (h/t https://twitter.com/J_ )
import java.lang.ref.WeakReference
/** An option-like type that doesn't keep
* the pointed item in scope
*/
trait WeakRef[+T] {
// If the reference is still live, return it, else None
def toOption: Option[T]
// If either reference is dead, return Empty, else give the live ref