tl;dr: How to compile a functional language via combinators (and evaluate via the Haskell runtime) while keeping the entire process type-indexed, with a bibliography and lots of references for further reading There is a long history, starting with Schönfinkel and Curry, of abstracting away variable names from lambda calculus terms by converting to combinators, aka bracket abstraction. This was popular in the 80’s as a compilation technique for functional languages (Turner, 1979; Augustsson, 1986; Jones, 1987; Diller, 1988), then apparently abandoned. More recently, however, it has been making ..read more

Continuing the series on dynamic programming, I just have a couple challenge problems for you today. I have indeed solved both of these problems in Haskell, but I don’t yet know how to write elegant solutions! There is a reason that the techniques covered in my previous posts aren’t quite good enough. Honi Assassins Feel free to discuss in the comments! I’m hoping that I can learn some new approaches from some of my readers. I will probably post some hints in the comments towards the right recurrences, so don’t look at the comments if you don’t want any spoilers ..read more

I’m finally getting around to reading Algorithm Design with Haskell (hereafter abbreviated as ADH), by Jeremy Gibbons and Richard Bird. I’ve had it for a while, and I have no excuse for waiting this long to read it, but anyway. I’m enjoying it so far, and wanted to share something I (indirectly) learned. I’m sure there are some who already know this, but I didn’t. I’ll share both the fun takeaway and then also the interesting, roundabout path I took to get there. Composed folds are nested folds Here’s the punchline: foldl :: (b -> a -> b) -> b -> [a] -> b foldl . foldl :: (b ..read more

This is part 2 of a promised multi-part series on dynamic programming in Haskell. As a reminder, we’re using Zapis as a sample problem. In this problem, we are given a sequence of opening and closing brackets (parens, square brackets, and curly braces) with question marks, and have to compute the number of different ways in which the question marks could be replaced by brackets to create valid, properly nested bracket sequences. Last time, we developed some code to efficiently solve this problem using a mutually recursive pair of a function and a lookup table represented by a lazy, immutable a ..read more

This is part 1 of a promised multi-part series on dynamic programming in Haskell. As a reminder, we’re using Zapis as a sample problem. In this problem, we are given a sequence of opening and closing brackets (parens, square brackets, and curly braces) with question marks, and have to compute the number of different ways in which the question marks could be replaced by brackets to create valid, properly nested bracket sequences. Last time, we developed a recurrence for this problem and saw some naive, directly recursive Haskell code for computing it. Although this naive version is technically ..read more

In my previous post, I challenged you to solve Zapis. In this problem, we are given a sequence of opening and closing brackets (parens, square brackets, and curly braces) with question marks, and have to compute the number of different ways in which the question marks could be replaced by brackets to create valid, properly nested bracket sequences. For example, given (??), the answer is 4: we could replace the question marks with any matched pair (either (), [], or {}), or we could replace them with )(, resulting in ()(). An annoying aside One very annoying thing to mention about this problem ..read more

In my previous post, I challenged you to solve Chemist’s Vows. In this problem, we have to decide which words can be made by concatenating atomic element symbols. So this is another parsing problem; but unlike the previous problem, element symbols are not prefix-free. For example, B and Be are both element symbols. So, if we see BE..., we don’t immediately know whether we should parse it as Be, or as B followed by an element that starts with E (such as Er). A first try A parsing problem, eh? Haskell actually shines in this area because of its nice parser combinator libraries. The Kattis enviro ..read more

tl;dr: if you appreciate my past or ongoing contributions to the Haskell community, please consider helping me get to ICFP by donating via my new ko-fi page! Working at a small liberal arts institution has some tremendous benefits (close interaction with motivated students, freedom to pursue the projects I want rather than jump through a bunch of hoops to get tenure, fantastic colleagues), and I love my job. But there are also downsides; the biggest ones for me are the difficulty of securing enough travel funding, and, relatedly, the difficulty of cultivating and maintaining collaborations. I ..read more

In my previous post, I challenged you to solve Alien Math, which is about reading numbers in some base , but with a twist. We are given a list of strings representing the names of the digits through , and a single string describing a number, consisting of concatenated digit names. For example, if and the names of the digits are zero, one, two, then we might be given a string like twotwozerotwoone, which we should interpret as . Crucially, we are also told that the digit names are prefix-free, that is, no digit name is a prefix of any other. But other than that, the digit names could be real ..read more

In my previous post, I challenged you to solve Letter Optimiztion. In this problem, we have a directed acyclic graph where each vertex represents a person, and there is an edge p -> q when person p sends their finished envelopes to person q. Also: Some people may send their envelopes to multiple other people, in which case they send a certain percentage of their output to each. Each person has a maximum speed at which they are able to process envelopes, measured in envelopes per second. The people with no inputs are assumed to have an infinite stack of envelopes and therefore work at their ..read more