Codes on Brandon Simmons' website

Sandbox Minus John Dillinger Equals What?

Fri, 12 Dec 2025 18:43:03 -0500

It didn’t look like anyone had ever tried to answer the question, so I thought I would have a go. This post probably won’t be interesting to folks already familiar with embeddings or linear algebra. It represents my rough, non-expert understanding of the subject matter

Huh. What could it mean to subtract two words, and how would you even do that? If we just consider the how, it’s not too hard to come up with a scheme. You could map a word to its place in the dictionary, say, then subtract the numbers and interpret the result N to mean the Nth word. But that’s not interesting, because alphabetical order (the basis of our mapping) is totally unrelated to a word’s meaning.

Linking Smaller Haskell Binaries

Sat, 07 Jan 2023 15:52:00 -0500

Haskell binaries can get quite large (think ~100MB), especially for projects with many transitive dependencies. Here are two strategies that can help at link time, the latter being more experimental.

I used the test-pandoc binary from pandoc on GHC 9.2.5 below. This was nice because obviously it was easy to test if linking broke anything (just run the tests).

`-split-sections` and `--gc-sections`

You can instruct ghc to emit code in individual minimal sections, allowing the linker to easily find and remove dead code. This looks like, in your cabal.project:

GHC LLVM LTO Experiments Scratch Notes

Sun, 02 Jun 2019 00:00:00 +0000

*This is a followup to this previous post where I play with GCC’s link-time optimization in GHC-compiled programs. I note there that this is limited since it only works on sources compiled from C (crucially the RTS). Here I’ve compiled rough notes doing the same thing with LLVM LTO, where I attempt to get true whole-program optimization *cooking.

The goals were to play with some new tech and possibly discover some significant performance gains (without thinking very hard) that could be ported back or realized in a less hacky way. Results were underwhelming and so I don’t do much real digging into assembly (the other thing besides good results that would have made for an interesting post). So after waffling I decided to basically dump my notes here, lightly edited, in case it’s helpful to someone who wants to take up similar work later.

A little tool for visualizing ghc verbose timing

Tue, 07 May 2019 00:00:00 +0000

I wrote a little tool to graph the fine-grained timing logs produced by ghc when the -v (verbose) flag is given. These logs to STDERR look like, e.g.

!!! Liberate case [Data.Binary.Class]: finished in 32.06 milliseconds, allocated 14.879 megabytes
!!! Simplifier [Data.Binary.Class]: finished in 873.97 milliseconds, allocated 563.867 megabytes

The project is on GitHub at jberryman/ghc-timing-treemap, along with a screenshot.

Navigating within the graph is pretty slow at least in firefox, and there are some other improvements that could be made, for instance some of the phases are run multiple times on the same module and it would be nice to see these grouped, where the module name is logged.

Initial hacking of GHC for GCC link-time optimization

Wed, 10 Apr 2019 00:00:00 +0000

I spent some time hacking GHC to use GCC’s link-time optimization, and wanted to share the results. The idea was to see whether we could get performance gains or other interesting results from :

cross module inlining, e.g. between C libraries from base and the RTS
GCC build flags that can only be added later, like -march=native to tailor optimizations to our microarchitecture
possibly nice interactions at barrier of haskell code and LTO’d C?

This was all very speculative, and the results you see below aren’t ultimately very interesting.

Hacking around on an FV-1 based guitar pedal

Sat, 26 Jan 2019 00:00:00 +0000

This is a diary-style post where I chronicle what I learn digging into a digital guitar effects pedal for the first time. I’m not sure how useful or interesting it will be to others.

I picked up an oddball modulation pedal from a “boutique” maker (being coy here) and decided there were a bunch of things I could improve about it, so I thought I’d try to tweak it. I know almost nothing about electronics.

Choosing a binary-to-text encoding

Sat, 22 Apr 2017 00:00:00 +0000

I had an occasion to think about text-friendly binary encoding schemes for the first time at work. The obvious choice is Base64, but my immediate subsequent thought was “there must be something much more efficient for our purposes”, and a quick google led here in which OP echos the same feeling:

It seems to me that we can greatly improve since on my keyboard I already see 94 easily distinguishable printable keys.

Almost inline ASM in haskell with foreign import prim

Sun, 12 Mar 2017 00:00:00 +0000

With help from Reid Barton in questions here and here I discovered it’s pretty easy to call assembly from GHC haskell with minimal overhead, so I cleaned up an example of this technique and posted it here:

https://github.com/jberryman/almost-inline-asm-haskell-example

This is especially useful if you want to return multiple values from a foreign procedure, where otherwise with the traditional FFI approach you would have to do some allocation and stuff the values into a struct or something. I find the above more understandable in any case.

Announcing: unagi-bloomfilter

Thu, 25 Aug 2016 00:00:00 +0000

I just released a new Haskell library called unagi-bloomfilter that is up now on hackage. You can install it with:

$ cabal install unagi-bloomfilter

The library uses the bloom-1 variant from “Fast Bloom Filters and Their Generalization” by Yan Qiao, et al. I’ll try to write more about it when I have the time. Also I just gave a talk on things I learned working on the project last night at the New York Haskell User Group:

Announcing: Hashabler 1.0. Now even more hashy with SipHash

Sun, 16 Aug 2015 00:00:00 +0000

I’ve just released version 1.0 of a haskell library for principled, cross-platform & extensible hashing of types. It is available on hackage, and can be installed with:

cabal install hashabler

(see my initial announcement post which has some motivation and pretty pictures)

You can see the CHANGELOG but the main change is an implementation of SipHash. It’s about as fast as our implementation of FNV-1a for bytestrings of length fifty and slightly faster when you get to length 1000 or so, so you should use it unless you’re wanting a hash with a simple implementation.

Translating some stateful bit-twiddling to haskell

Fri, 03 Jul 2015 00:00:00 +0000

I just started implementing SipHash in hashabler and wanted to share a nice way I found to translate stateful bit-twiddling code in C (which makes heavy use of bitwise assignment operators) to haskell.

I was working from the reference implementation. As you can see statefulness and mutability are an implicit part of how the algorithm is defined, as it modifies the states of the v variables.

#define SIPROUND                                        \
  do {                                                  \
    v0 += v1; v1=ROTL(v1,13); v1 ^= v0; v0=ROTL(v0,32); \
    v2 += v3; v3=ROTL(v3,16); v3 ^= v2;                 \
    v0 += v3; v3=ROTL(v3,21); v3 ^= v0;                 \
    v2 += v1; v1=ROTL(v1,17); v1 ^= v2; v2=ROTL(v2,32); \
  } while(0)

int  siphash( uint8_t *out, const uint8_t *in, uint64_t inlen, const uint8_t *k )
{

  /* ... */

  for ( ; in != end; in += 8 )
  {
    m = U8TO64_LE( in );
    v3 ^= m;

    TRACE;
    for( i=0; i<cROUNDS; ++i ) SIPROUND;

    v0 ^= m;
  }

I wanted to translate this sort of code as directly as possible (I’d already decided if it didn’t work on the first try I would burn my laptop and live in the woods, rather than debug this crap).

Announcing hashabler: like hashable only more so

Thu, 30 Apr 2015 00:00:00 +0000

I’ve just released the first version of a haskell library for principled, cross-platform & extensible hashing of types, which includes an implementation of the FNV-1a algorithm. It is available on hackage, and can be installed with:

cabal install hashabler

hashabler is a rewrite of the hashable library by Milan Straka and Johan Tibell, having the following goals:

Extensibility; it should be easy to implement a new hashing algorithm on any Hashable type, for instance if one needed more hash bits

Benchmarking very fast things with criterion

Thu, 05 Mar 2015 00:00:00 +0000

There’s a pervasive myth that Bryan O’Sullivan’s excellent haskell benchmarking library criterion is only useful for benchmarks that take some significant chunk of time (I’ve even heard some people claim on the ms scale). In fact criterion is useful for almost anything you’d want to benchmark.

At a high level criterion makes your benchmark the inner loop of a function, and runs that loop a bunch of times, measures the result, and then divides by the number of iterations it performed. The approach is both useful for comparing alternative implementations, and probably the only meaningful way of answering “how long does this code take to run”, short of looking at the assembly and counting the instructions and consulting your processor’s manual.

Announcing unagi-chan

Tue, 07 Oct 2014 00:00:00 +0000

Today I released version 0.2 of unagi-chan, a haskell library implementing fast and scalable FIFO queues with a nice and familiar API. It is available on hackage and you can install it with:

$ cabal install unagi-chan

This version provides a bounded queue variant (and closes issue #1!) that has performance on par with the other variants in the library. This is something I’m somewhat proud of, considering that the standard TBQueue is not only significantly slower than e.g. TQueue, but also was seen to livelock at a fairly low level of concurrency (and so is not included in the benchmark suite).

Thoughts on FIFO-ness

Mon, 03 Feb 2014 00:00:00 +0000

I’ve been doing a lot of experimenting with concurrent operations in haskell and in particular playing with and thinking about the design of concurrent FIFO queues. These structures are difficult to make both efficient and correct, due to the effects of contention on the parts of the structure tasked with coordinating reads and writes from multiple threads.

These are my thoughts so far on FIFO semantics.

FIFO? And how!

In the interesting paper “How FIFO is your concurrent FIFO queue?”(PDF). A Haas, et al. propose that an ideal FIFO queue has operations that are instantaneous (think of each write having an infinitely accurate timestamp, and each read taking the corresponding element in timestamp order). They then measure the degree to which real queues of various designs deviate from this platonic FIFO semantics in their message ordering, using a metric they call “element-fairness”. They experimentally measure element-fairness of both so-called “strict FIFO” as well as “relaxed FIFO” designs, in which elements are read in more or less the order they were written (some providing guarantees of degree of re-ordering, others not).

Announcing shapely-data v0.1

Mon, 23 Dec 2013 00:00:00 +0000

This is the first real release shapely-data, a haskell library up here on hackage for working with algebraic datatypes in a simple generic form made up of haskell’s primitive product, sum and unit types: (,), Either, and ().

You can install it with

cabal install shapely-data

Motivation and examples

In order from most to least important to me, here are the concerns that motivated the library:

Provide a good story for (,)/Either as a lingua franca generic representation that other library writers can use without dependencies, encouraging abstractions in terms of products and sums (motivated specifically by my work on simple-actors.

Writing a streaming twitter waterflow solution

Mon, 18 Nov 2013 00:00:00 +0000

In this post Philip Nilsson describes an inspiring, principled approach to solving a toy problem posed in a programming interview. I wanted to implement a solution to a variant of the problem where we’d like to process a stream. It was pretty easy to sketch a solution out on paper but Philip’s solution was invaluable in testing and debugging my implementation. (See also Chris Done’s mind-melting loeb approach)

My goal was to have a function:

A TypeFamilies Primer

Mon, 12 Aug 2013 00:00:00 +0000

TypeFamilies is a GHC extension that lets you create formerly-impossible abstractions in a very straightforward way. It took me several tries before they clicked for me though, so this is the introduction to TypeFamilies that I wish I had read first (although I just found Brent Yorgey’s, which would have done the trick).

I’m treating the subject very narrowly for most of this post, and try to round things out a little at the very end.

Thinking about an economy of bit flips

Sun, 17 Mar 2013 00:00:00 +0000

Disclaimer: un-researched, under-educated, fast and loose hacking follows.

The other day I was thinking about counting in binary and how bits cascade when incrementing a counter.

I wondered: what if each bit flip was very “expensive”, for the hardware say? Are there other methods we could use that woud result in a “cheaper” increment operation, by avoiding those costly carries?

First, here’s a little bit of boring code that we’ll use below to print a list of Ints as padded binary, and some requisite imports:

Using GHC's RebindableSyntax for a dynamic state "Fauxnad"

Sun, 10 Feb 2013 00:00:00 +0000

I just learned about GHC’s RebindableSyntax extension from chrisdoner’s thread on reddit and wanted to play around with scratching a couple itches I’ve had. In this post I’ll illustrate using RebindableSyntax to allow us to use haskell’s do notation in a State-monad-like construction, in which our state type is allowed to change (I’ve played with this idea previously).

The dynamic state construction looks like the traditional State, but with separate types for input and output state:

dilly.js: a library for loops with delays in JavaScript

Tue, 09 Oct 2012 00:00:00 +0000

I’ve released a new library for writing sort of idiomatic-looking loops with delays in javascript. This was motivated by this work in which I was implementing an algorithm/simulation; I wanted the code to be readable as straighforward loops, but I needed a delay for the visual portion.

Here is an example of its usage:

withDelay(1000).endingWith(other_stuff)                  
    .for("x",1,2)                // range: 1, 2
        .for("y",1,3 , 8)        // range(with step of 2): 1, 3, 5, 7
            .for("z",['a','b'])  // foreach: 'a', 'b'
                .do(function(){ 
                    console.log(this.var("x"), 
                                this.var("y"), 
                                this.var("z"));
                 });

The inner do block runs with a one-second delay between executions.

Making your zipper disappear with Zippo

Mon, 17 Sep 2012 00:00:00 +0000

I’ve finally had a chance to look at how my new lens-based, power-packed, minimal zipper library zippo looks when compiled, and initial results are pleasing!

For example, here is a silly zipper operation that increments the nodes of a sort-of tree:

module Main where

import Control.Category((>>>))
import Data.Lens.Zipper
import Data.Yall.Lens

data Tree a = Br { _lBranch :: NodeBr a
                 , _rBranch :: NodeBr a }
            deriving Show

data NodeBr a = NodeBr { _node :: a }
    deriving Show

-- START BOILERPLATE
lBranch = lens _lBranch (\(Br _ r) l-> Br l r)
rBranch = lens _rBranch (\(Br l _) r-> Br l r)
node = lens _node $ const NodeBr
-- END BOILERPLATE

-- example data:
t = Br (NodeBr 1 ) (NodeBr 3 )

-- zipper operations
incNode = moveP node >>> modf (+1) >>> moveUp
zops = zipper >>> moveP lBranch >>> incNode >>> moveUp >>> 
        moveP rBranch >>> incNode >>> close

main = print $ zops t

When compiled with

simple-actors 0.4.0: a few interesting design bits

Wed, 22 Aug 2012 00:00:00 +0000

simple-actors is my library for more structured concurrent programming based on the Actor model. It’s been a fun vehicle for exploring concurrent semantics, and an opportunity to solve some tricky API design problems in pretty clever ways. I want to present a handful of these problems, and the solutions I came up with, below.

Short digression: I love distributed systems, but this library has nothing to do with distributed programming. Also performance.

zippo: a lightweight lens-based, type-checked, heterogenous zipper

Mon, 28 May 2012 00:00:00 +0000

I finished this new zipper library which you can get with a

cabal install zippo

and fork it on github.

After working for a long time on pez, I wanted to try a zipper library that was also based on lenses, but where heterogenous move up operations would be type-checked, as would a move up past the “top” of the structure.

It looks as though instant-zipper is the only other zipper package that provides that kind of type safety.

A Simulation of a Biological MIS Algorithm

Mon, 14 May 2012 00:00:00 +0000

I’ve finished a simulation-visualization of the very cool algorithm for generating a Maximal Independant Set from “A Biological Solution to a Fundamental Distributed Computing Problem” by Afek et al. (sorry I don’t have a link to the PDF, and respect you too much to link you to a paywall).

You can play with it or check out the code on GitHub; in particular, see “algorithm.js” for the didactic implementation of the algorithm.

It uses jQuery and Raphael.js for the visuals and events.

Converting HTML5 canvas elements to images

Mon, 30 Apr 2012 00:00:00 +0000

I recently needed to do some conversions/processing to a bunch of HTML files, which contained html canvas images, so I needed a way of converting all the canvas elements on the page to PNGs.

After a bit of research and tweaking, the following worked well enough for me:

{% gist 2561736 %}

Run it in your browser’s JS console on the page you want to process (we assume jQuery is already loaded on the page).

Announcing yet another lens library

Wed, 04 Apr 2012 00:00:00 +0000

I just uploaded the first version of a lens library I’ve been working on, called yall. You can get it with a

cabal install yall

or check it out on github. There will be a Template Haskell library for automatically deriving lenses at some point in the future.

I was motivated primarily by the desire for a lens that is acceptable for pez (existing libs such as the excellent fclabels or data-lens didn’t fit the bill for assorted reasons), and to explore some abstractions and generalizations re lenses more deeply.

the Monoid instance for Ordering

Mon, 02 Apr 2012 00:00:00 +0000

I was just looking at the Monoid docs, when I found an instance that surprised me: Ordering.

Here is how it’s defined:

-- lexicographical ordering
instance Monoid Ordering where
        mempty         = EQ
        LT `mappend` _ = LT
        EQ `mappend` y = y
        GT `mappend` _ = GT

Without the comment I don’t know if I would have gotten it right away, but check this out:

Prelude> :m + Data.Monoid 
Prelude Data.Monoid> zipWith compare "asff" "asdf"
[EQ,EQ,GT,EQ]
Prelude Data.Monoid> let compare' s = mconcat . zipWith compare s
Prelude Data.Monoid> compare' "asff" "asdf"
GT

A string comparison function can be defined using the comparisons of corresponding letters (, numbers, etc.) as Monoids.

Optimization fun: Minimum Edit Distance

Tue, 20 Mar 2012 00:00:00 +0000

I’m doing Stanford’s free online [NLP class](NLP class), and last week’s lesson introduced Levenshtein Distance and the traditional matrix-based algorithm. I implemented the algorithm in haskell to get a better understanding of it, but then got a bit obsessive about optimizing.

I wanted to develop an approach iteratively so I’d learn something along the way, but I didn’t take great pains to document the process very well, nor do I have any analysis here of low level details.

shapely-data: a library for structuralizing Haskell data types

Tue, 06 Mar 2012 00:00:00 +0000

This was a quick, on-a-whim sort of project that ended up taking me all week, as I learned my way around template haskell. It felt like trying to make a sandwich with your feet for the first time, and was about as traumatizing.

Anyway the result is my library named shapely-data which you can get with the usual…

cabal install shapely-data

and is up on github here.

The library can be used to convert an algebraic data type into a form that replaces its constructors with a combination of (,), Either and (). See the haddocks for usage information, and implementation details.

Categories that want to be Arrows

Sat, 11 Feb 2012 00:00:00 +0000

This is me recording some half-formed thoughts that have been rattling around in my head for the last week. They concern haskell’s Arrow typeclass; in particular it’s frustrating inability to be applied to types that are in Category but have no suitable implementation for arr.

Consider something as simple as:

newtype Bij a b = Bij (a -> b) (b -> a)

a Category instance is trivial, but an Arrow instance is impossible, since we would need to supply a b -> a given only a a -> b.

How the Haskell Prelude avoids overlapping instances in Show

Mon, 06 Feb 2012 00:00:00 +0000

In reading about overlapping instances in haskell, I came across this proposal that mentioned that:

[Overlapping types] can sometimes be simulated with the extra-method trick used in the Show class of the Prelude for showing lists of characters differently than lists of other things.

I’d never thought about how haskell-98 can support a show "asdf" that returns

"\"asdf\""

while show [1,2,3,4] returns

"[1,2,3,4]"

And I was surprised at the complexity of Show when I looked at the docs and implementation (to be honest, I had no idea how the class was implemented or that show was not the only method).

Haskell state of the Lens, etc.

Tue, 31 Jan 2012 00:00:00 +0000

For my own purposes, I wanted to take a tour of all the various formulations of lenses on hackage and thought I would post the lightly-curated results here. I just grepped the package list page for the following terms: lens, label, record, accessor, editor, and reference. Some were not sufficiently general to include here.

Here were the ones implementing “lens-like” functionality, loosely in order of my opinion on their usefulness for my own purposes:

pez v0.1.0 released

Sun, 29 Jan 2012 00:00:00 +0000

pez is a powerful, generic zipper library that can be used with a minimum of boilerplate, using fclabels lenses as an interface. This new version supports fclabels 1.0 and uses the new lenses supporting failure.

The API has changed significantly, but should be more stable at this point. You can try it with a:

$ cabal install pez

You can find the code on github here. I will try to post some fun examples here in the next week or two.

simple-actors 0.1.0 released

Tue, 11 Oct 2011 00:00:00 +0000

Just a quick announcement of the release of simple-actors, a DSL-style haskell library for more structured concurrent programs via the Actor Model. You can fork it on github, and install it via cabal with a

cabal install simple-actors

This version is significantly more coherent, powerful and simple than the original 0.0.1 version (which was something I just whipped together for a blog post I haven’t gotten around to writing yet).

Let me know if you have any comments or suggestions!

A brief tutorial-introduction to 'fclabels' 1.0

Sun, 21 Aug 2011 00:00:00 +0000

Sebastiaan Visser et al. last week announced the release of v1.0 of fclabels. This is a short introduction to the changes for people who are already somewhat familiar with the package.

Que? The fclabels package is a haskell library providing “first class labels” for haskell data types and some Template Haskell code for automatically generating said labels. This makes for a more composable and much more powerful alternative to haskell’s built-in record syntactic sugar. Here is a good introductory tutorial.

Module 'chan-split' released

Sun, 17 Jul 2011 00:00:00 +0000

Whaa?

chan-split is a haskell library that is a wrapper around Control.Concurrent.Chans that separates a Chan into a readable side and a writable side.

We also provide two other modules: Data.Cofunctor (because there didn’t seem to be one anywhere), and Control.Concurrent.Chan.Class. The latter creates two classes: ReadableChan and WritableChan, making the fundamental chan functions polymorphic, and defining an instance for standard Chan as well as MVar (an MVar is a singleton bounded channel, wanna fight about it?).

simple-actors: a simple Actor Model concurrency library

Mon, 30 May 2011 00:00:00 +0000

EDIT: I’ve just released version 0.1.0 of this library. It is a complete re-write / re-think that I think makes the library much more attractive, simple and powerful. There won’t be any more dramatic API changes.

I was in need of a simple, tight library implementing the Actor Model of concurrency and didn’t find one on hackage, so I wrote my own. You can check out the docs here and get it with a

Magic Haskell code completions in Vim!

Sat, 07 May 2011 00:00:00 +0000

UPDATE: This project is on hold for now. Many people have pointed out that the snipMate VIM plugin can probably handle many of these completions. I may make a collection of those at some point, but I no longer have much interest in finishing this.

I’m trying something new: putting code-in-progress up on github while I work on it. So! I love haskell so freaking much I’ve started creating a vimscript to improve the typeability of the language in the vim editor, and the working name is: haskomplete.vim

PEZ: the Potentially-Excellent Zipper library release

Tue, 19 Apr 2011 00:00:00 +0000

I’m happy to announce the release of a zipper library I namedPEZ! I’ve been learning and building this silly library almost as long as I’ve been learning haskell. It’s not as great as it could be, but I’m releasing it now because it’s about time.

You can check it out with a:

cabal install pez

The library provides a generic zipper that can be used on all types in the Typeable class, for which the user defines (or generates) lenses from the excellent fclabels package.

Synchronized Concurrent IO Actions

Thu, 24 Feb 2011 00:00:00 +0000

This is a bit of literate haskell code that works through a system for running concurrent IO computations that are synchronized on a stream. So we have many “nodes” of the type :: a -> IO () running concurrently on a single stream, where we would like each node to wait until all nodes have processed a stream element before any are allowed to proceed onto the next element.

This was motivated by the desire to simulate a system in which many nodes are interacting independently according to a time-synchronized algorithm. So the “stream” the nodes process is time.

When is it okay to 'fail'?

Wed, 16 Feb 2011 00:00:00 +0000

That’s the question.

In designing a couple libraries the question of the proper use of the Monad class’s fail method has come up more than once.

On the one hand, many people consider fail to be a wart on the face of an otherwise pure implementation of an elegant construction borrowed from category theory. It’s as if someone defined scissors as

“two metal blades with handles, attached by a pivot… plus a bandaid in case you cut yourself”.

New version of directory-tree on hackage

Sun, 13 Feb 2011 00:00:00 +0000

In response to a request and my own review I’ve modified my directory-tree package as follows:

Eq and Ord instances now compare on free “contents” type variable
we provide equalShape function for comparison of shape and filenames of arbitrary trees (ignoring free “contents” variable)
provide a comparingShape used in sortDirShape
provide a sortDirShape function that sorts a tree, taking into account the free file “contents” data

Now that equality and comparison functions that ignore the contents of Files are out of the Eq and Ord instances, we can make those types of comparisons on DirTrees of different types.

Do Applicative Functors generalize the S & K Combinators?

Sun, 02 Jan 2011 00:00:00 +0000

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. Away from the computer I got out a pad of paper and went about trying to figure out how the <*> method was defined over functions. Here are the types:

Working with Template Haskell in GHCi

Tue, 14 Dec 2010 00:00:00 +0000

I’ve just started trying to learn and debug Template Haskell and found it a bit rough trying to explore TH interactively, but a couple of things have helped.

First and most obvious, we can use runQ to see the abstract TH syntax which a quasi-quoted expression expands to:

Prelude> :set -XTemplateHaskell
Prelude> :m + Language.Haskell.TH
Prelude Language.Haskell.TH> runQ [| \a -> a+1 |]
LamE [VarP a_1] (InfixE (Just (VarE a_1)) (VarE GHC.Num.+) (Just (LitE (IntegerL 1))))

The second thing that was really helpful to me was turning on the dump- splices debugging option which causes GHC to print the expansions of all $(top-level splices):

A State Monad with dynamically-typed state

Thu, 09 Dec 2010 00:00:00 +0000

Haskell’s standard State monad types allow the programmer to define a computation that works with some state in a way that looks and feels similar to using mutable state in an imperative language. However these State monad types are limited in that the type of the state cannot change during the computation.

Normally this is fine, but what if we really wanted to use the mechanics of a state monad to pass some state value that changed type, e.g. some mutually- recursive tree structure we would like to traverse?:

New version of 'thrist' package released

Sat, 13 Nov 2010 00:00:00 +0000

I’ve been collaborating with Gabor Greif on a new version of his ’thrist’ module, which was just released last night! I approached Gabor with some new ideas that came to me as I was writing a module that uses Thrists heavily, and he invited me to co-author this version. (See below for a brief explanation of Thrists).

I noticed that in the previous version, the function foldThrist was essentially a foldr with a type signature that was overly restrictive.

Designing a Module for Combinatory Logic in Haskell

Sat, 04 Sep 2010 00:00:00 +0000

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:

Repairing NetbookInstaller's Chameleon Bootloader

Fri, 27 Aug 2010 00:00:00 +0000

If you have set up your hackintosh using Meklort’s NetbookBootMaker / NetbookInstaller and have overwritten the Chameleon bootloader with GRUB or have otherwise damaged your MBR, you can use some of the following techniques to fix your issues.

NetbookInstaller uses a custom version of Chameleon to patch the Mac OS kernel in memory during bootup. If you have accidentally installed GRUB (or another bootloader) to your MBR, you will probably find it is impossible to boot into your OS X partition.

17x17: some Simulated Annealing updates

Sat, 31 Jul 2010 00:00:00 +0000

Note: this is part of a series of posts is related to the “17x17 Challenge” posted by Bill Gasarch. The goal is to color cells of a 17 by 17 grid, using only four colors, such that no rectangle is formed from four cells of the same color.

Just a few follow-ups to my previous post in which I use a simulated annealing-type algorithm to find a good (hopefully complete) cover of a grid by swapping rows and columns from four identical sub-grids of 74 colors.

The Gift of Inconsistency

Thu, 22 Jul 2010 00:00:00 +0000

Computer science is a fascinating and maddening thing. Even the most seemingly-esoteric topics turn out to be fundamental. Go out to the fringes of CS and you find yourself smack in the middle of Philosophy. You try to understand a single point and you suddenly find yourself embracing everything.

So this post comes from that infinitely-recursive rabbit hole of wikipedia topics I’ve been falling down for the last few weeks, and you can probably expect a few more like this one; I’ll try to keep focused.

17x17: A Simulated Annealing approach using thresholds

Sat, 10 Jul 2010 00:00:00 +0000

This is something I’ve been wanting to play with for months now, but haven’t made the time to implement: I wondered if simulated annealing techniques could be effective in finding a complete grid covering.

17x17: Further Thoughts & Some Pretty Pictures

Tue, 01 Jun 2010 00:00:00 +0000

An almost silly amount of time passes between my new ideas on this problem and investigating/coding those ideas, but I’m trying to be better about helping my thoughts see the light of day before I get entirely bored of them.

Befunge-93 Interpreter on Hackage

Thu, 20 May 2010 00:00:00 +0000

I’ve fixed a bug related to upgrading GHC to version 6.12 (thanks to Cale and the folks on haskell-cafe who helped me with the issue) and got my Befunge-93 interpreter up on hackage. The program is written in haskell (as usual). You should be able to get it soon with a:

$ cabal install Befunge93

If you want to read about how I designed it you can check out the source above, or take a look at my previous blog post.

Code Jam 2010: Incrementing a Binary Counter

Sun, 09 May 2010 00:00:00 +0000

The Problem

Problem A in the qualifying round of this year’s Google CodeJam contest was really clever. The problem used a classic made-for-TV gadget from the 80s: The Clapper™ (“snapper” in google’s version) and went like this:

The Snapper is a clever little device that, on one side, plugs its input plug into an output socket, and, on the other side, exposes an output socket for plugging in a light or other device.

17x17: Some Attempts at Doubly-Symmetrical Rotations

Fri, 09 Apr 2010 00:00:00 +0000

Note: this is part of a series of posts is related to the " 17x17 Challenge" posted by Bill Gasarch. The goal is to color cells of a 17 by 17 grid, using only four colors, such that no rectangle is formed from four cells of the same color.

In a previous post I presented rotations of some single-color rectangle-free grids which were symmetrical along a diagonal axis. I also noticed that, of the single-colorings of optimal size which I could generate, all with an odd number side-length could be made symmetrical along both diagonals (the evens could not):

Lazy Arithmetic in Haskell

Wed, 24 Mar 2010 00:00:00 +0000

We don’t usually give much thought to Numeric data types beyond whether we want to work with integers or decimal numbers. And that is a shame! In this post I’ll look at how we can actually do arithmetic operations lazily, and in the process hopefully reveal a bit about haskell’s numeric classes.

module LazyArithmetic
    where

We will be using Lennart Augustsson’s numbers library which can be installed from hackage with cabal-install:

17x17: More about symmetry and a new rotation

Thu, 18 Mar 2010 00:00:00 +0000

This is part of a series of posts is related to the " 17x17 Challenge" posted by Bill Gasarch. The goal is to color cells of a 17 by 17 grid, using only four colors, such that no rectangle is formed from four cells of the same color.

In my last post, I gave a symmetrical rotation of the known 74-cell single-coloring. I want to use a slight variation of that grid to show why I think treating the grids as symmetrical will help us in solving this problem.

17x17: Symmetric Single-Colorings and some Graph Theory

Sun, 14 Mar 2010 00:00:00 +0000

This is part of a series of posts is related to the “17x17 Challenge” posted by Bill Gasarch. The goal is to color cells of a 17 by 17 grid, using only four colors, such that no rectangle is formed from four cells of the same color.

In my last post I noticed that all of the smaller optimal single-colorings I generated showed diagonal symmetry, meaning that row 1 is the same as column 1, row 8 is the same as column 8, etc. It’s my hypothesis that all complete single-colorings are symmetrical in this way.

17x17: Some Thoughts on the Problem

Sun, 07 Mar 2010 00:00:00 +0000

I’ve been puzzling over some of the problems presented by the 17 x 17 Challenge, and wanted to share some of what I’ve learned and have been wondering about. The problem and ultimate goal is to color a 17 x 17 grid with four colors such that every cell is colored and no rectangle is formed by any four cells of the same color.

Single-Color Subsets

I’ve started by trying to find an algorithm to find optimal single-color subsets, i.e. a way of coloring a grid with one color such that no rectangle is formed by the colored cells, and we have the greatest number of cells colored as possible. I started thinking of coloring cells one at a time, following a path based on the notion of an “extended rectangle” where the fourth side was longer or shorter than the first, to avoid forming rectangles.

17x17: Deterministic algorithm for single-coloring a grid

Mon, 01 Mar 2010 00:00:00 +0000

I finally got some time to code up a messy script to test out a few variations of an algorithm to generate rectangle-free single colorings of a grid, as part of a ~~lazy~~ humble effort to solve the 17 x 17 challenge.

This post is going to be a bit of a code-dump. The algorithm is essentially:

color cell,
turn to the right,
stop on first non-rectangle forming cell,
if the cell is uncolored, color it and turn to the right, else if the cell was already colored and has been entered from this direction already, then skip it, else turn to the right

17x17: Brute Force Algorithm for an Optimal Rectangle-Free Subset

Tue, 23 Feb 2010 00:00:00 +0000

I’ve been making notes when I have time, on the “17 x 17 challenge” posted a couple months back by Bill Gasarch. I’ve been sketching out algorithms for the problem and wanted to quickly produce some optimal rectangle free subsets to check my work and look at. So the code below answers the following question:

Imagine an n x n grid. You can color cells of the grid such that no rectangle overlayed on the grid will have all four corners colored. Find a grid with the maximum possible colored cells.

An alternative definition for Data.List.groupBy

Wed, 10 Feb 2010 00:00:00 +0000

The function groupBy from haskell’s standard library is defined in terms of span, the effect being that the supplied predicate function is used to compare the first element of a group with successive elements.

This isn’t clear from the docs, and you might try to do this and wonder at the output you got:

*Main> groupBy (< =) [3,4,5,3,2,1,4,4,1,1,2,3,4,5,4,5,6,7]
[[3,4,5,3],[2],[1,4,4,1,1,2,3,4,5,4,5,6,7]]

We can redefine groupBy as follows, so that the supplied predicate function compares adjacent elements one-by-one and returns True if they should be grouped together:

The Definition of Data.List.group

Sat, 06 Feb 2010 00:00:00 +0000

I’ve been thinking quite a bit lately about a category of functions that are always a bit awkward to define: they involve cases where we would like to traverse a recursive data structure and do something with the data that we have passed over but which is “gone now”. There are many examples of functions like these in the haskell standard libraries: [span](http://haskell.org/ghc/docs/latest/html/libraries/base-4.2.0.0/src/GHC-List.html#span), [splitAt](http://haskell.org/ghc/docs/latest/html/libraries/base-4.2.0.0/src/GHC-List.html#splitAt), etc.

A function like group is in this category. It’s conceptually very simple, but defining it actually requires a bit of indirection. Here I’ve translated the definition from Data.List to use explicit recursion:

A Befunge-93 Interpreter

Sun, 31 Jan 2010 00:00:00 +0000

I just finished an initial release of an interpreter for the befunge programming language, based on the ‘93 spec. The project was quite fun! My goal was to produce a well-designed program with performance that didn’t suck too bad. Here are some highlights:

Design

I found that writing the core functionality of the interpreter took almost no time, once I settled on the approach I would take. I used a monad transformer for the first time, StateT:

DeBruijn Sequences pt.3 - The "Prefer Opposite" algorithm

Wed, 02 Dec 2009 00:00:00 +0000

This is the third post of mine on DeBruijn sequences, and is in preparation for another post to come which I hope should be an interesting investigation into a possible parallel algorithm. The first two posts are here and here.

This algorithm works identically to the Prefer One algorithm, however rather than choose a 1-bit if possible, we instead choose the opposite bit from the previous bit, if possible.

This has the effect of evening out the locations of the zeros and ones throughout the sequence. We will exploit this in a later post where I will explore a possible parallel algorithm, which should be interesting I hope!

Find a permutation given its Inversion Table

Sun, 15 Nov 2009 00:00:00 +0000

Here is some code I whipped up in response to an interesting problem posted on reddit.com/r/coding/. It was a really interesting algorithm to work out:

import Data.List (sortBy)
  
-- takes an inversion list and converts it to the list of permuted  
-- elements:  
decode = dec [] . sortBy lowHi . zip [1..] where
    dec as [] = as
    dec as ((a,_):is) = let is' = sortBy lowHi (decrementGT a is)
                         in dec (a:as) is'
  
-- decrement every inversion number by 1, for every tuple in which  
-- the element is greater than `a`:  
decrementGT a = map (\(a',i) -> (a', if a'>a then i-1 else i) )
  
-- we sort by the inversion number, low to high. For elements with  
-- the same inversion number, we say that the greater element tuple  
-- should go before a lesser element:  
lowHi (a,i) (a',i')
    | i == i' = if a>a' then LT else GT
    | otherwise = compare i i'

It’s not the prettiest code I’ve written, but it’s pretty straight-forward and concise. Thanks for looking!

An "Adaptive" Move-to-Front Algorithm

Fri, 13 Nov 2009 00:00:00 +0000

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.

The move-to-front (MTF) Transform

Tue, 10 Nov 2009 00:00:00 +0000

To follow up my last post about the Burrows-Wheeler Transform, I decided to implement another simple algorithm which is often used after the BWT to help consolidate localized redundancy in the data before entropy encoding.

The idea behind the Move-to-Front algorithm is that we start with some known alphabet (like the list of ASCII characters), and encode our data elements as the index into that alphabet list of each element. The trick is that after each character is encoded, the alphabet list is modified by moving the element whose index we just looked up to the front of the alphabet.

Polishing a Functional Pearl: The Burrows-Wheeler Transform

Sat, 07 Nov 2009 00:00:00 +0000

Here is a quick post to get me back into the swing of blogging.

I was looking through an old post on StackOverflow about clever functional code, and the best answer, given by “yairchu” was a nice version of the Burrows-Wheeler Transform, which is an algorithm for permuting a string such that it can be compressed more effectively by other algorithms. The code posted was (import Data.List assumed):

bwp :: (Ord a)=> [a] -> [a]
bwp xs = map snd $ sort $ zip (rots xs) (rrot xs)
rots xs = take (length xs) (iterate lrot xs)
lrot xs = tail xs ++ [head xs]
rrot xs = last xs : init xs

I saw I could improve/shorten this in a couple of obvious ways and came up with this:

The State Monad: a tutorial for the confused?

Sat, 24 Oct 2009 00:00:00 +0000

I’ve written this ~~brief~~ tutorial on haskell’s State monad to help bridge some of the elusive gaps that I encountered in other explanations I’ve read, and to try to cut through all the sticky abstraction. This is written for someone who has a good understanding of the Maybe and List monads, but has gotten stuck trying to understand State. I hope it’s helpful!

The Data Declaration:

To understand a monad you look at its datatype and then at the definition for bind (>>=). Most monad tutorials start by showing you the data declaration of a State s a in passing, as if it needed no explanation:

Cracking a Lock in Haskell with the De Bruijn sequence, pt. 2

Tue, 29 Sep 2009 00:00:00 +0000

For this post I will rework the Prefer One algorithm from the previous post so that it is much more efficient. We will add words to a Patricia Tree-like dictionary as we see them, passing the tree along in the State monad; to check if a new word has been seen we simply check in the tree, rather than in the array.

First, a little boilerplate…

> module Main
> where
>
> import Data.Array
> import Data.List(isInfixOf, tails)
>
> import Control.Monad.State
> import Control.Arrow

NEW IMPLEMENTATION:

In the previous implementation, to check if the word formed by adding a one has been seen, we had to iterate through each of the previous bits in the array, checking words.

Cracking a Lock in Haskell with the De Bruijn sequence, pt. 1

Thu, 24 Sep 2009 00:00:00 +0000

date = “a” slug = “a/cracking-a-lock-in-haskell-with-the-de-bruijn-sequence-pt-1” Part 2.

A De Bruijn sequence is (for example) a cyclical list of characters such that every word of a given length appears once and only once in the sequence. Instead of using letters, you can have a De Bruijn sequence of bits. For example here is one possibility for a sequence in which every 3-bit word appears somewhere (you have to wrap around from the end for the final “words”):

Proposed modification to 'array' function in Data.Array

Tue, 22 Sep 2009 00:00:00 +0000

In Data.Array the function array :: (IArray a e, Ix i) => (i, i) -> [(i, e)] -> a i e takes the array bounds and an association list, and it produces an Array. The function allows you to build an Array by providing the elements in whatever order you choose, rather than from the first index to the last.

The function listArray is similar except that it assumes that the list is already ordered by index so there is no need to provide tuples of (index, value). Becase listArray actually uses zip internally to produce the tupled list, so the programmer can pass a list to listArray which exceeds the declared bounds of the array and the function will quietly drop the extra list tail:

Some Haskell Boilerplate For Google CodeJam

Sat, 22 Aug 2009 00:00:00 +0000

I put together a skeleton module which should be usable for any of the problems in this year’s Google CodeJam Programming Contest (as long as they don’t adopt a new format/pattern for the problems this year). The module includes some useful parsing functions which should in the worst case be useful as a cheatsheet for those not too experienced with Parsec (*cough me). I hope it will encourage people to sign up and use Haskell in the contest!

List Grouping module released

Fri, 14 Aug 2009 00:00:00 +0000

EDIT: Don’t use this package, but use instead Data.List.Split by Brent Yorgey. I didn’t see that a package like his existed! This module will hopefully be removed from hackage if they can do that.

I just finished the initial release of a simple module called list-grouping that contains functions to partition a list into sub-lists in various ways, based on some predicate or integer offset. Functions like these are a little awkward to write and I was surprised when I didn’t see anything on hackage!

Enumerating all n-integer Sets Which Sum to an Integer x

Thu, 30 Jul 2009 00:00:00 +0000

I came up with what I think is an elegant use of monadic code, while working on a program to compute solutions to the Postage Stamp Problem. The problem asks:

Consider that an envelope is able to hold a limited number of postage stamps. Then, consider the set of the values of the stamps – positive integers only. Then, what is the smallest total postage which cannot be put onto the envelope?

Fun with Lazy Arrays: the LZ77 Algorithm

Thu, 18 Jun 2009 00:00:00 +0000

This is my third post investigating compression techniques related to the DEFLATE algorithm: the first on run-length encoding, and the second on simple Huffman Coding. This post models the LZ77 algorithm, the second of the two compression strategies used by DEFLATE, and in the process explores some interesting properties of Haskell’s basic Arrays.

Implementation:

> module LZ77
>     where
  
we will use GHC's "basic non-strict arrays" for this
experiment:
  
> import Data.Array

and use Ints to store the length of the entire decoded
message (needed to create our array):
  
> type Length = Int
> type Offset = Int
  
in place of the length in the standard length-offset pair
I've decided to use an Int representing the index of the
last element in the span relative to the element at
offset. Thus the pair encoding a span of only one element,
two elements back would be (0,2), rather than the more
traditional (1,2).

This simply makes more sense to me, especially since I want
to be able to encoded reversed sequences, as you will see.

> type Index = Int
  
and a few simple dataypes for our uncompressed and
compressed data respectively:
  
> type Decoded a = Array Index a
>
> data Encoded a = Enc Length [ Either a (Index,Offset) ]
  
The decompress function works by traversing the encoded message,
keeping track of our array index position (since offsets are
relative to the current position), and building an Array lazily
from a list which we generate, in part by referencing elements
from the partially generated array itself.
  
So when we see a Right value we look up in the Array the elements
referenced by the length-offset, concat-ing that list with the
result of processing the rest of the encoded message.
  
If we hit [] in 'dec' we call an error because the stored value
for the length of the uncompressed message in the Encoded type
was longer than what the 'decompress' function could produce.

It's diffficult to describe, but I hope the code is clear:
  
> decompress :: Encoded a -> Decoded a
> decompress (Enc el es) = decoded
>     where decoded = listArray (0,el - 1) $ dec 0 es
>             dec _ [] = error "message is shorter than it should be"
>             dec n (Left x : xs) = x : dec (n+1) xs
>             dec n (Right (iRel,off) : xs) =
>                 let i1 = n - off
>                     i2 = (if iN > i1 then succ else pred) i1
>                     iN = i1 + iRel
>                  in [ decoded!i | i <- [i1, i2 .. iN] ] ++ dec (n + 1 + abs iRel) xs

Some interesting things about the code above:

Huffman Coding

Sun, 31 May 2009 00:00:00 +0000

This is the second of probably three posts (the first was on run-length encoding in Haskell) inspired by Thomas Guest’s interesting article on the Deflate algorithm. This is also my first post in literate haskell. Please post any improvements to the code if you have them! For a refreshingly readable introduction to Huffman Coding and the Deflate algorithm, have a look at this short explanation by Antaeus Feldspar.

First some boilerplate…

> module Huffman
>     where

> import Data.List (sort, insert)
> import qualified Data.Map as M
> import Data.Function (on)
> import Control.Arrow (second)

We make an abstract datatype for binary digits. I wonder if this would
be a nice (but slow?) way of working with binary IO. There doesn't seem
to be a package on Hackage for this

  
> data Bit = O | I
>          deriving (Show, Ord, Eq)

we define a simple binary tree useful for decoding the encoded binary
stream. the simple algorithm for assigning codes to our symbols
produces this tree. A completed tree for some text containing only
three letter might look like this:


         0    /\   1
             /\ A
            C B

  
> data HTree a = Branch {zer :: (HTree a), 
>                        one :: (HTree a),
>                        wt :: Int }
>              | Leaf {symb :: a, wt :: Int }
>              deriving (Show)


maps from <Symbol> to <Binary Code>, we create this from the HTree
built from the list of weighted symbols. the HTree can't be used for
encoding.
  
> type CodeDict a = M.Map a [Bit]
 

Now some instance declarations so that we know how to order (by weight):
  
> instance Ord (HTree a) where
>     compare = compare `on` wt
>
> instance Eq (HTree a) where
>     (==) = (==) `on` wt

our function for merging two branches which we use to build the HTree
from the list of symbols and their corresponding weights. no point in
defining a Monoid instance, but we'll tip our hat to it:
  
> mappend t1 t2 = Branch t1 t2 (wt t1 + wt t2)

Building the Coding Trees

We assign codes to our weighted symbols using a simple algorithm
which takes the trees (initially Leaves) with the lowest weights
and combines them (and their weights) and inserts them back into
the list until they have been combined into a single tree:

  
> buildDecTree :: [(a,Int)] -> HTree a
> buildDecTree = build . sort . map (uncurry Leaf)
>     where build (t:[]) = t
>           build (t1:t2:ts) = build $ insert (t1 `mappend` t2) ts
  
  
now convert the binary tree representation to a dictionary form for
encoding. we decompose the tree into a list from the top down, mapping
either a 1 or 0 over the flattened children. a little confusing:
  
> buildEncDict :: (Ord a) => HTree a -> CodeDict a
> buildEncDict = M.fromList . build
>     where build (Leaf t _) = (t,[]) : []
>           build (Branch a b _) = mapBit O a ++ mapBit I b
>           -- build up the codes in the snd of each Leaf's tuple:
>           mapBit b = map (second (b:)) . build

(En/De)coding Functions

To encode a list of symbols for which we've generated an HTree, we just
map over it, looking up it's code in our Map dictionary:
  
> encode :: (Ord a) => CodeDict a -> [a] -> [Bit]
> encode d = concatMap (d M.!)
  
  
To decode we simply read a Bit at a time from the input, at the same time
traversing the HTree (going left when we encounter a zero, and vice versa).
When we hit a Leaf (the end of a code) we return the symbol and go onto
the next bit from the top of the HTree once again.
  
> decode :: HTree a -> [Bit] -> [a]
> decode t [] = []
> decode t bs = dec bs t
>     where dec bs' (Leaf x _) = x : decode t bs'
>           dec (O:bs') (Branch l _ _) = dec bs' l
>           dec (I:bs') (Branch _ r _) = dec bs' r

Usage Examples

UPDATE: I scrapped and re-did this section. Should be a little better now.:

Run-length Encoding

Tue, 26 May 2009 00:00:00 +0000

Just a quick implementation of a RLE algorithm for lists in haskell. We compress a list by converting “runs” of consecutive elements into a tuple of the form: (run length, element).

import Data.List (group)
import Control.Arrow
  
runLengthEnc :: Eq a => [a] -> [(Int,a)]
runLengthEnc = map (length &&& head) . group
  
decode :: [(Int, a)] -> [a]
decode = concatMap (uncurry replicate)

If the &&& combinator looks foreign to you, check out David R. Maciver’s very enlightening blog about Arrow functions.

Partial Application and a simple Mastermind game

Sun, 17 May 2009 00:00:00 +0000

I thought this was a good, simple example of how currying and partial application can be used in a very expressive way. We create a one-liner to play the game mastermind.

In the type signature we include unnecessary parentheses, to be clear that we are thinking of the function not as “a function taking a secret code and a guess and returning a score for the guess” but as “a function taking a secret code and returning a scoring function for that code”.

Gnome Sort

Mon, 11 May 2009 00:00:00 +0000

In my boredom, I implemented the toy sorting algorithm called Gnome Sort. It accomplishes backtracking by using a zipper-like system of two lists treated as stacks, and is about 100X slower than GHC’s merge sort on the test I used. It’s also not especially small or simple-looking. It’s basically terrible:

gnomeSort :: (Ord a)=> [a] -> [a]
gnomeSort = sort []
    where sort rs [] = rs
          sort [] (x:xs) = sort [x] xs
          sort (r:rs) (x:xs)
              | x > r = sort rs (x:r:xs)
              | otherwise = sort (x:r:rs) xs

The above doesn’t keep track of where it left off before it began to backtrack, an obvious optimization which turned the algorithm into an insertion sort:

directory-tree module released

Sat, 09 May 2009 00:00:00 +0000

I’ve released my first package, up now on hackage (haddock docs should be generated soon). The module provides a simple data structure that mirrors a directory tree, and some useful functions for doing IO on directories of files. You can read more about it here.

It’s very likely there are some bugs, especially related to cross platform issues with file names and paths. The module is also fairly bare, so please send me any requests for functionality that I haven’t thought of, as well as any bugs you might find.

a DirectoryTree module and some examples

Thu, 30 Apr 2009 00:00:00 +0000

UPDATE: I’ve just released this as my first package on hackage. You can read more and write any comments here.

I just put together a library that provides a simple tree data structure to represent the structure of files and directories in the OS. It provides some simple IO functions like readDirectory (analogous to readFile) which “opens” a directory, returning a DirTree of Strings in the IO monad.

The nice thing is that by defining a simple instance for Traversable (and the default instances for Foldable and Functor that we get for free) we get a whole array of nice functions which we can apply to directory structures! For example, we can combine all the text in a directory of files with:

Why I love Hoogle

Sat, 25 Apr 2009 00:00:00 +0000

I’m working on a module called DirectoryTree, a simple tree structure mirroring the structure of a directory tree in the outside world, with functions to hopefully make it easy to do useful things (I’m not sure if something like this already exists). Here is the data-type:

data DirTree a = Dir { name :: String,
                       files :: [a],
                       directories :: [DirTree a] }
               | Fail String --file/directory name

I would like to do things like map over a DirTree of FilePaths, returning a tree (in the IO monad) of Handles… so the code involves a lot of slogging through the IO monad, which I’m not totally comfortable with yet.

Initial tests of Tries: Follow Up

Sat, 18 Apr 2009 00:00:00 +0000

This is to wrap up my previous post about Tries and my attempts at an implementation, and to summarize some of the things I think I learned about implementing a Trie structure in Haskell.

Complexity is Slow

My initial idea of using a container type at each node to store the collection of branches was a good idea for testing (I could easily swap in Data.Map, or my own simple binary tree) and convenience (I could use Data.Map’s built-in functions to insert the element of the list key into the the container); but it turned out to be bad for performance.

Some initial tests of Tries

Thu, 16 Apr 2009 00:00:00 +0000

I have been interested in writing a Trie implementation to see how its performance compares to using Data.Map for storing dictionary-like data. I wrote a minimal implementation of Tries which exports insert,insertWith, and lookup definitions and can be used in place of Data.Map for those functions. I tested the implementation using a program frequency.hs which reads a source file and uses insertWith on each word to count the frequency of the words in a file; we then use lookup to print out the frequencies of a list of arbitrary words.

Cycle Detection

Sun, 12 Apr 2009 00:00:00 +0000

The Algorithm

We can use Brent’s Algorithm to detect infinitely-repeating sequences in a list of values generated by some iterated function: that is, any list in which the next value in the sequence is generated from the previous value alone; if we find duplicate values in the list, we know we have a cycle.

The implementation below isn’t particularly elegant, and since I want to use it as a stand-alone tool I’m having it output strings:

Parallel List Comprehensions with a Monte Carlo example

Wed, 08 Apr 2009 00:00:00 +0000

GHC has an extension to the list comprehensions syntax that replicates the functionality of zipWith, by allowing you to have two generators running in parallel. Turn on the extension in GHCi like so:

Prelude> :set -XParallelListComp

I use the extension below to generate an infinite list of random coordinates (scaled to a 1000x1000 grid) using two different Linear Congruential Generators running in parallel. It should be simple to modify the code below to actually run the generators concurrently using Data Parallel Haskell (although I haven’t had a chance to play with that yet).

The Total Recall combinator

Wed, 01 Apr 2009 00:00:00 +0000

infixr 9 .:
(.:) :: (b -> c) -> (a -> a1 -> b) -> a -> a1 -> c
(.:) = (.)(.)(.)

This can be used to compose a string of functions with a binary function stuck on the end. For example:

lookupPlusOne :: (Ord k, Monad m, Num n) => k -> Map k n -> m n
lookupPlusOne = liftM (+1) .: lookup

(picked up from some folks on #haskell)

Building a Tree from an Ordered List

Tue, 31 Mar 2009 00:00:00 +0000

A nice recursive algorithm for building a nearly-optimal binary search tree from an ordered list.:

data Tree a = Node a (Tree a) (Tree a)
            | End

The algorithm divides the input list into sublists of increasing length: 1,2,4,8… The first element of each sublist is the “keystone” of a subtree assembled with mkTree. :

fromSorted :: [a] -> Tree a
fromSorted = foldl mkTree End . divide 1
    where mkTree l (n:ns) = Node n l (fromSorted ns)
          divide _ [] = []
          divide c xs = take c xs : divide (c*2) (drop c xs)

Variations that used splitAt instead of the separate take and drop were no more efficient (perhaps because of sharing?) nor was using the strict foldl'.

Data.Map Conversion Functionality

Sun, 29 Mar 2009 00:00:00 +0000

There are three identical functions in Data.Map for flattening a Map to a list of tuples in ascending order:

assocs = toList = toAscList

…but nothing to convert to a descending list.