the arc of software bends towards understanding
In today’s world of social news aggregation websites, ala Reddit, Digg, Slashdot, it is rare for the sole dialog between an author and a reader to take place on a private channel or on one’s website. I discovered this rather bluntly when I found that a document I had written had amassed a number of comments, one of which pointed out an error in what I had written, and then failed to notify me.
Conductor and violinist Gustavo Dudamel will be visiting MIT today to accept the Eugene McDermott Award in the Arts. Part of the awards ceremony will include a session with Dudamel conducting the MIT Symphony Orchestra; I’ll be on stage playing Oboe and English Horn on Rimsky Korsakov and Mozart. Our regular conductor (Adam Boyles) has been prepping us for this by taking, erm, unusual liberties in tempo and phrasing.
I’m not usually very aware of names of conductors, but I have heard Dudamel’s float across WQXR on occasion. The evening promises to be exciting.
data-accessor is a package that makes records not suck. Instead of this code:
newRecord = record {field = newVal}
You can write this:
newRecord = field ^= newVal
$ record
In particular, (field ^= newVal) is now a value, not a bit of extra syntax, that you can treat as a first-class citizen.
I came across this module while attempting to use Chart (of criterion fame) to graph some data. I didn’t recognize it at first, though; it was only after playing around with code samples did I realize that ^= was not a combinator that Chart had invented for its own use (as opposed to the potpourri of -->, <+>, ||| and friends you might see in an xmonad.hs). When utilized with Template Haskell, Data.Accessor represents something of a replacement for the normal record system, and so it’s useful to know when a module speaks this other language. Signs that you’re in a module using Data.Accessor:
Earlier in January, I blogged some first impressions about the VX-8R. It’s now three months later, and I’ve used my radio on some more extensive field tests. I’m considering selling my VX-8R for a 7R, for the following reasons:
I really am going to miss the dedicated stereo jack and slimmer (and, in my opinion, better) interface, but these really are deal breakers. C’ést la vie.
Two people have asked me how drew the diagrams for my previous post You Could Have Invented Zippers, and I figured I’d share it with a little more elaboration to the world, since it’s certainly been a bit of experimentation before I found a way that worked for me.
Diagramming software for Linux sucks. Those of you on Mac OS X can churn out eye-poppingly beautiful diagrams using OmniGraffle; the best we can do is some dinky GraphViz output, or maybe if we have a lot of time, a painstakingly crafted SVG file from Inkscape. This takes too long for my taste.
In the beginning, there was a binary tree:
struct ctree { // c for children
int val;
struct ctree *left;
struct ctree *right;
}
The flow of pointers ran naturally from the root of the tree to the leaves, and it was easy as blueberry pie to walk to the children of a node.
Unfortunately, given a node, there was no good way to find out its parent! If you only needed efficient parent access, though, you could just use a single pointer in the other direction:
zip: List<A>, List<B> -> List<(A, B)>
zip(Nil, Nil) = Nil
zip(_, Nil) = Nil
zip(Nil, _) = Nil
zip(Cons(a, as), Cons(b, bs)) = Cons((a, b), zip(as, bs))
fst: (A, B) -> A
fst((a, _)) = a
last: List<A> -> A
last(Cons(a, Nil)) = a
last(Cons(a, as)) = last(as)
foldl: (B, A -> B), B, List<A> -> B
foldl(_, z, Nil) = z
foldl(f, z, Cons(x, xs)) = foldl(f, f(z, x), xs)
Good grief Edward, what do you have there? It’s almost as if it were some bastardized hybrid of Haskell, Java and ML.
I’m happy to report that I’ll be interning at Galois over the summer. I’m not quite sure how the name of the company passed into my consciousness, but at some point in January I decided it would be really cool to work at an all-Haskell shop, and began pestering Don Stewart (and Galois’s HR) for the next two months.
I’ll be working on some project within Cryptol; there were a few specific project ideas tossed around though it’s not clear if they’ll have already finished one of my projects by the time the summer rolls around. I’m also really looking forward to working in an environment with a much higher emphasis towards research, since I need to figure out if I’m going to start gunning for a PhD program at the end of my undergraduate program.
Code written by Anders Kaseorg.
In The Three Projections of Doctor Futamura, Dan Piponi treats non-programmers to an explanation to the Futamura projections, a series of mind-bending applications of partial evaluation. Go over and read it if you haven’t already; this post is intended as a spiritual successor to that one, in which we write some Haskell code.
The pictorial type of a mint. In the original post, Piponi drew out machines which took various coins, templates or other machines as inputs, and gave out coins or machines as outputs. Let’s rewrite the definition in something that looks a little bit more like a Haskell type.
The fast, efficient association map has long been the holy grail of the functional programming community. If you wanted such an abstract data structure in an imperative language, there would be no question about it: you would use a hash table. But the fact that the hash table is founded upon the destructive update makes it hard to use with pure code.
What we are in search of is a strictly more powerful association map, one that implements a non-destructive update (i.e. is “persistent”). In the Haskell world, Data.Map is a reasonably compelling general-purpose structure that only requires the Ord typeclass on its keys. For keys that map cleanly on to machine-size integers, IntMap is an extremely fast purely functional that uses bit twiddling tricks on top of big-endian Patricia tries.