- Probabilistic Data Structures for Web Analytics and Data Mining : A great overview of the space of probabilistic data structures and how they are used in approximation algorithm implementation.
- Models and Issues in Data Stream Systems
- Philippe Flajolet’s contribution to streaming algorithms : A presentation by Jérémie Lumbroso that visits some of the hostorical perspectives and how it all began with Flajolet
- Approximate Frequency Counts over Data Streams by Gurmeet Singh Manku & Rajeev Motwani : One of the early papers on the subject.
- [Methods for Finding Frequent Items in Data Streams](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.187.9800&rep=rep1&t
{------------------------------------------------ | |
A Haskell solution to: http://www.coinheist.com/rubik/a_regular_crossword/grid.pdf | |
using the Z3 SMT solver. | |
Z3 finds the following solution in about 7 mins | |
on my Mac Core-i5, and another 7 mins to prove | |
it's unique. | |
NHPEHAS | |
DIOMOMTH |
This is material to go along with a 2014 Boston Haskell talk.
We are going to look at a series of type signatures in Haskell and explore how parametricity (or lack thereof) lets us constrain what a function is allowed to do.
Let's start with a decidedly non-generic function signature. What are the possible implementations of this function which typecheck?
wrangle :: Int -> Int
// Define the general Arg type and companion object: | |
import language.higherKinds, language.implicitConversions, language.existentials | |
object Arg { implicit def toArg[Tc[_], T: Tc](t: T): Arg[T, Tc] = Arg(t, implicitly[Tc[T]]) } | |
case class Arg[T, Tc[_]](value: T, typeclass: Tc[T]) | |
// Say, for example we have a typeclass for getting the length of something, with a few instances | |
trait Lengthable[T] { def length(t: T): Int } | |
implicit val intLength = new Lengthable[Int] { def length(i: Int) = 1 } | |
implicit val stringLength = new Lengthable[String] { def length(s: String) = s.length } |
module Catenable (Catenable, empty, singleton, toList, fromList, uncons, unsnoc) where | |
import Data.List (foldl') | |
import Control.Monad | |
-- | Trivial catenable sequence. Supports O(1) append, and (amortized) | |
-- O(1) `uncons`, and `unsnoc`, such that walking the sequence via | |
-- N successive `uncons` steps or N `unsnoc` steps takes O(N). Like a | |
-- difference list, conversion to a `[a]` takes linear time, regardless | |
-- of how the sequence is built up. |
import cats._ | |
import implicits._ | |
import shapeless._ | |
import tag._ | |
import scala.language.dynamics | |
import cats.effect.IO | |
trait Var[F[_], A] extends Dynamic { outer => |
I was recently asked to explain why I felt disappointed by Haskell, as a language. And, well. Crucified for crucified, I might as well criticise Haskell publicly.
First though, I need to make it explicit that I claim no particular skill with the language - I will in fact vehemently (and convincingly!) argue that I'm a terrible Haskell programmer. And what I'm about to explain is not meant as The Truth, but my current understanding, potentially flawed, incomplete, or flat out incorrect. I welcome any attempt at proving me wrong, because when I dislike something that so many clever people worship, it's usually because I missed an important detail.
Another important point is that this is not meant to convey the idea that Haskell is a bad language. I do feel, however, that the vocal, and sometimes aggressive, reverence in which it's held might lead people to have unreasonable expectations. It certainly was my case, and the reason I'm writing this.
I love the concept of type class
{-# LANGUAGE | |
LambdaCase | |
, OverloadedLists | |
, OverloadedStrings | |
, RecordWildCards | |
, BlockArguments | |
, DeriveFunctor | |
, TypeApplications | |
, GeneralizedNewtypeDeriving | |
#-} |
// Need to be able to support different AST types | |
class LanguageAbstraction { | |
type Term | |
type Apply | |
} | |
// Equivalent to case class Foo[A](value: A), but with two additional properties: | |
// - L <: LanguageAbstraction, for letting us specify the language of what's inside | |
// - Z , for letting us describe the type of what's inside | |
case class Phantom[A, L <: LanguageAbstraction, Z](value: A) |