Edward Kmett

Haskell programmer, mathematician, lapsed graphics guru and demo scener, defense contractor and financial toolsmith.

  • Unlifted Structures 27 Aug 2015

    How to build a strict universe with cheap pointers inside of Haskell
  • Moore Machines

    No description given.

  • How to Replace Failure by a Heap of Successes 2 May 2015

    This post explains the notion of an Update Monad as a way to think about how to write a parser, then it uses the special meaning of the particular update language for the parser to make the parser more efficient.
  • Fibonacci

    It is more or less a joke that all that functional programmers care about are ways to compute the Fibonacci numbers. ```haskell fibs = 1:1:zipWith (+) fibs (tail fibs) ``` Our primary benchmark suite for Haskell is named `nofib` after all. But what if we embrace this predilection? What tools and powers do we gain?
  • Cache-Oblivious Data Structures

    Cache-Oblivious Data Structures show that by optimizing for any one cache with unknown parameters you simultaneously optimize for all caches asymptotically. As we get more and more caches, this model becomes more and more "true" over time, and the ability for hand-written code to exceed it by using the cache parameters is lessened by each additional cache we add to the system.
  • Editorials

    Posts of a more polemic nature
  • PHOAS For Free 9 Dec 2013

    This post revisits the PHOAS and splits it into more compositional components using profunctors that enable us to have a Monad for capture avoiding substitution despite using HOAS.
  • Bound 2 Dec 2015

    This post talks about how to make a form of generalized de Bruijn indices that are fit for human consumption.
  • Cellular Automata

    This is a short series in which I'm exploring ways some interesting structures in Haskell using cellular automata as motivating examples.
  • Conquering Folds 13 Sep 2013

    In this post I show how you can fold almost anything with a Comonad that should permit us to execute a large class of divide-and-conquer algorithms in parallel.
  • On-line Lowest Common Ancestor 27 Aug 2015

    On-line lowest common ancestor search has been traditionally viewed as an O(h) operation. We can use purely functional data structures to transform it into an O(log h) form, opening up new use-cases.
  • Parallel and Incremental CRCs 11 Sep 2013

    In this post I work through a novel algorithm for computing CRCs incrementally and in parallel.
  • Recursion Schemes

    These posts may eventually grow into a taxonomy of recursion schemes. For now it consists of an old Knol on catamorphisms that I wrote that no longer has a home.
  • Revisiting Matrix Multiplication

    This series is a rather lazy exploration of how to work with sparse data in Morton order. Along the way we'll be composing a number of useful data structures and twiddling a lot of bits.
  • Snippets

    This is a holding bin for short interactive code-snippets that aren't worth a whole tutorial.