wkimeria

git clone git@github.com:wkimeria/gitout.git
cd gitout
git checkout -b wkimeria_working
Switched to a new branch 'wkimeria_working'

wkimeria

Quick and dirty way of finding gaps in sequential rows (using sqlite as an example)

Imagine you have a table that contains data with a monotonically increasing key. You can write some quick SQL code (I'll use sqlite3) to tell whether you have any gaps in the sequence of ids.

create table sequential(id int not null, name varchar(10) null);

delete from sequential;
insert into sequential(id, name) select 1, "one";
insert into sequential(id, name) select 2, "two";

wkimeria

def maximum(tr: Tree[Int]): Int = tr match{
  case Leaf(v) => v
  case Branch(l,r) => maximum(l) max maximum(r)	
}

wkimeria

def size[A](tr: Tree[A]): Int = tr match{
  case Leaf(_) => 1
  case Branch(l, r) => 1 + size(l) + size(r)
}

wkimeria

def sizeViaFold[A](t: Tree[A]): Int = 
  fold(t)(a => 1)(1 + _ + _)

wkimeria

/* 
Like `foldRight` for lists, `fold` receives a "handler" for each of the data constructors of the type, and recursively
accumulates some value using these handlers. As with `foldRight`, `fold(t)(Leaf(_))(Branch(_,_)) == t`, and we can use
this function to implement just about any recursive function that would otherwise be defined by pattern matching.
*/
def fold[A,B](t: Tree[A])(f: A => B)(g: (B,B) => B): B = t match {
  case Leaf(a) => f(a)
  case Branch(l,r) => g(fold(l)(f)(g), fold(r)(f)(g))
}

wkimeria

sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

wkimeria

def foldLeftViaFoldRight[A,B](l: List[A], z: B)(f: (B,A) => B): B =
  foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)

wkimeria

def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = {
  def loop[A](supRev: List[A], subRev: List[A], isSubSequence: Boolean): Boolean = supRev match {
    case Nil => {
      subRev match {
        case Nil => isSubSequence
        case _ => false
      }
    }
    case Cons(x,xs) => subRev match {
      case Nil => isSubSequence

wkimeria

def reverse[A](as: List[A]): List[A] = as match {
  case Nil => Nil
  case Cons(x, xs) => foldLeft(xs, Cons(x,Nil))((a,b) => Cons(b, a))
}

def foldRightViaFoldLeft[A,B](as: List[A], z: B)(f: (B, A) => B): B = 
  foldLeft(reverse(as), z)((b,a) => f(b,a))

def map[A,B](as: List[A])(f: A => B): List[B] = 
  foldRightViaFoldLeft(as, Nil:List[B])((t,h) => Cons(f(h),t))