Instantly share code, notes, and snippets.

@yellowflash
yellowflash / SpatialMap.scala
Last active Jun 27, 2018
Spatial Index with geo hash
View SpatialMap.scala
import scala.annotation.tailrec
import scala.collection.mutable
case class Point(x: Int, y: Int) {
def geoHash(precision: Int): BigInt = {
@tailrec
def hash(minX: Int, maxX: Int, minY: Int, maxY: Int, prec: Int, sofar: BigInt) : BigInt = {
if(prec == 0) return sofar;
val quadrant = if((minX + maxX)/2 < x) {
if((minY + maxY)/2 < y) 0 else 1
@yellowflash
yellowflash / Regex.js
Last active Jun 27, 2018
A derivative based regex matching
View Regex.js
class Regex {
constructor(matchesEmpty) {
this.matchesEmpty = matchesEmpty;
}
derivativeBy(ch) {
throw "Not implemented";
}
matches(str) {
@yellowflash
yellowflash / Map.js
Created May 16, 2018
Hash map with linear probing
View Map.js
class Map {
constructor(loadfactor = 0.7) {
this.size = 0;
this.loadfactor = 0.7;
this.entries = new Array(1);
}
put(key, value) {
this.resizeIfNecessary();
for(var i = key.hashCode();; i++) {
@yellowflash
yellowflash / Godel.purs
Last active Oct 11, 2018
Purescript implementation of a dependent typed language.
View Godel.purs
module Godel.Core where
import Control.Monad (bind, pure)
import Control.Monad.Eff.Console (log)
import Data.Either (Either(..))
import Data.Eq (class Eq, (==))
import Data.Map (Map, empty, insert, lookup)
import Data.Maybe (Maybe(..))
import Data.Show (class Show, show)
import Prelude (otherwise, negate, (+), (-), (>=), ($), (<>))
View Cont.scala
package cont
import scala.util.Try
abstract class Cont[A] {
def run[R](cont: A => R): R
def map[B](fn: A => B): Cont[B] = {
val self = this
new Cont[B] {def run[R](cont: B => R) = self.run(cont compose fn)}
}
@yellowflash
yellowflash / RegExp.scala
Last active Sep 1, 2018
Regex Engine which runs in `O(mn)` Glushkov automaton
View RegExp.scala
sealed trait RegExp {
def isFinal:Boolean
def acceptsEmpty:Boolean
def shift(prev:Boolean, character:Char):RegExp
def matches(str:String) =
if(str.isEmpty) this.acceptsEmpty
else str.foldLeft(this.shift(true, str.head))(_.shift(false,_)).isFinal
}
object Epsilon extends RegExp {
View Functor.scala
trait Functor[T, F[_]] { self: F[T] =>
def map[K](fn: T => K): F[K]
}
sealed trait Optional[+T] extends Functor[T, Optional]
case class Maybe[T](value:T) extends Optional[T] {
override def map[K](fn: T => K) = Maybe(fn(value))
}
case object Nope extends Optional[Nothing] {
View SKIEquivalence.scala
package skiequivalence
sealed trait SKIExpression {
def convert:SKIExpression
def freeVariables:Set[TermVariable]
}
case class TermVariable(variable:String) extends SKIExpression {
override def convert = this
override def freeVariables = Set(this)
View Tautology.hs
import Data.List
import Data.Char
data Prop = Const Bool
|Var Char
|Not Prop
|And Prop Prop
|Implies Prop Prop
deriving Show