Inside 736-131

Existential Pontification and Generalized Abstract Digressions


Let’s play a game

Ever wondered how Haskellers are magically able to figure out the implementation of functions just by looking at their type signature? Well, now you can learn this ability too. Let’s play a game. You are an inventor, world renowned for your ability to make machines that transform things into other things. You are a proposer. […]

  • September 5, 2011

8 ways to report errors in Haskell revisited

In 2007, Eric Kidd wrote a quite popular article named 8 ways to report errors in Haskell. However, it has been four years since the original publication of the article. Does this affect the veracity of the original article? Some names have changed, and some of the original advice given may have been a bit... […]

  • August 29, 2011

Joseph and the Amazing Technicolor Box

Consider the following data type in Haskell: data Box a = B a How many computable functions of type Box a -> Box a are there? If we strictly use denotational semantics, there are seven: But if we furthermore distinguish the source of the bottom (a very operational notion), some functions with the same denotation […]

  • August 23, 2011

Changes to IntMap

As it stands, it is impossible to define certain value-strict operations on IntMaps with the current containers API. The reader is invited, for example, to try efficiently implementing map :: (a -> b) -> IntMap a -> IntMap b, in such a way that for a non-bottom and non-empty map m, (\_ -> undefined) […]

  • August 1, 2011

Variant types and GADTs

OCaml supports anonymous variant types, of the form type a = [`Foo of int | `Bar of bool], with the appropriate subtyping relations. Subtyping is, in general, kind of tricky, so I have been using these variant types fairly conservatively. (Even if a feature gives you too much rope, it can be manageable and useful […]

  • July 22, 2011

Parallelism to plug space leaks

It is not too difficult (scroll to “Non sequitur”) to create a combinator which combines two folds into a single fold that operates on a single input list in one pass. This is pretty important if your input list is pretty big, since doing the folds separately could result in a space leak, as might […]

  • July 15, 2011

IVar leaks

The first thing to convince yourself of is that there actually is a problem with the code I posted last week. Since this is a memory leak, we need to keep track of creations and accesses of IVars. An IVar allocation occurs in the following cases for our example: Invocation of return, which returns a […]

  • July 4, 2011

Scheduling IVars

One downside to the stupid scheduler I mentioned in the previous IVar monad post was that it would easily stack overflow, since it stored all pending operations on the stack. We can explicitly move all of these pending callbacks to the heap by reifying the execution schedule. This involves adding Schedule state to our monad […]

  • July 1, 2011

The IVar monad

An IVar is an immutable variable; you write once, and read many times. In the Par monad framework, we use a prompt monad style construction in order to encode various operations on IVars, which deterministic parallel code in this framework might use. The question I'm interested in this post is an alternative encoding of this […]

  • June 29, 2011

A pattern for increasing sharing

I recently encountered the following pattern while writing some Haskell code, and was surprised to find there was not really any support for it in the standard libraries. I don’t know what it’s called (neither did Simon Peyton-Jones, when I mentioned it to him), so if someone does know, please shout out. The pattern is […]

  • June 17, 2011