fragmentary ideas ䷿ intellectual what-nots ䷷ and haskell programming ䷴

If the title hasn't scared you off yet, here's the story: I was hacking on someone else's code on the plane and trying to wrap my head around some Applicative class code; in particular the code in question used the Applicative instance for ((->) a) i.e. functions. This turned my brain to cream-of-wheat and I had to take a break.

If you aren't familiar with Applicative Functors, they are somewhere in between the familiar and simple Functor class and the Monad class; an abstraction for function application with a context. Check out here for more.
Read the rest of this article »

Like the Lambda Calculus (on which Lisp is based), Combinatory Logic is a formal system that can be used to model and study computation. What makes it fascinating is that it is as powerful as the (already simple) lambda calculus, but has no need for the variables that LC requires to perform substitution!

Here I show how we can use Haskell’s type classes and other language features to model the Combinator Calculus. The goals of this module were:

1. don’t force any one evaluation strategy
2. allow users to define new combinators without exposing the implementation
3. allow new combinators to be defined in terms of other already-defined combinators.
4. discourage creation of non-sensical combinator expressions, or possible mis-use of the module
5. hide existential types and anything else exotic

If you want to play with it, you can do a:

$> darcs get http://coder.bsimmons.name/code/CombinatorCalculus

Read the rest of this article »

UPDATE: Thanks to steve for pointing out that the scheme I describe here is essentially the same as Algorithm BSTW.

I came up with this variation of the Move-to-Front transform which doesn’t require that there be a known alphabet of symbols. Instead it builds up the alphabet as it goes along and encounters a new symbol. I’m sure that this is a known algorithm, as it’s a fairly obvious variation, but I don’t know what the proper name for it is, so I’m calling it an Adaptive Move-to-Front.

I’m very interested in hearing if this is similar or identical to any other algorithms, so if anyone has any insights, please comment!

Differences from the Standard MTF Transform:

The traditional MTF algorithm, as I understand it, uses some known ordered alphabet of symbols (e.g. the bytes from 0-255, or the letters a-z), so presumably, one need not store this alphabet along with the encoded/compressed data.

With the algorithm I describe here though, the final permutation of the alphabet list, output by the encoder, must be retained to decode the message. The encoded message is identical to the output of the traditional MTF transform, except where a symbol is encoded which has not appeared previously.

Here we have zipped the output of the standard MTF (the fst) with the adaptive version (the snd) to make it easy to compare elements:

Message: “the rrrrain in sssspain falls maaiinly on the plain”

Output (standard MTF, adaptive):

[(116,0),(105,1),(103,2),(35,3),(115,4),(0,0),(0,0),(0,0),(101,5),(107,6),(112,7),(4,4),(2,2),(2,2),(2,2),(116,8),(0,0),(0,0),(0,0),(115,9),(5,5),(5,5),(5,5),(5,5),(109,10),(4,4),(113,11),(0,0),(7,7),(4,4),(114,12),(4,4),(0,0),(7,7),(0,0),(7,7),(6,6),(121,13),(6,6),(116,14),(4,4),(2,2),(14,14),(14,14),(14,14),(3,3),(13,13),(8,8),(10,10),(10,10),(8,8)]

The standard algorithm was working with the ASCII alphabet, so each new symbol is located somewhere far back into the alphabet; it is then moved to the front. In the adaptive version, when we see a new symbol, it is automatically made the next in our running alphabet and then of course moved to the front.

This means that with the adaptive version, for any given stretch from the beginning of the encoded message, we are using the minimal number of different index integers to encode the stream, always choosing the next greatest integer when we require a new one. Here is the output of the adaptive version alone:

Encoded phrase:

[0,1,2,3,4,0,0,0,5,6,7,4,2,2,2,8,0,0,0,9,5,5,5,5,10,4,
11,0,7,4,12,4,0,7,0,7,6,13,6,14,4,2,14,14,14,3,13,8,
10,10,8]

Final permutation of minimal dictionary list:
"nialp ehtoymsfr"

What these means for actual compression schemes on a binary level, I have no idea, but I would like to explore this topic much more. Without further ado, here is some code.

The Encoder:

This “adaptive move-to-front” encoder works in the same way as the standard algorithm, except that we start out with an empty alphabet list and build it up as we see new elements not yet in our list.

Essentially if, while searching for an element, we hit the empty list [], we pretend that the element we were looking for was at the end of the list.

This is exactly what happens in the traditional algorithm: when we try to encode a symbol that we haven’t yet encountered, we venture into a new part of the alphabet list that we haven’t touched yet.

The Decoder

Our decoder requires that we pass it the final permutation of the symbol list, along with the encoded list of indexes. It then simply does the reverse of the encoding function.

To decode we follow these steps:

1. Return the head of the list of symbols
2. Re-insert the symbol into the index location specified by the head of the encoded/index list
3. Move on to the next encoded index, using the new list of symbols. go to (1)