On the road to functional programming enlightenment, I discovered two beautiful one-liners for depth-first and breadth-first search in Haskell. Here they are:

dfs, bfs :: (a -> [a]) -> a -> [a]
dfs succ start = start : concatMap (dfs succ) (succ start)
bfs succ start = concat $takeWhile (not . null)$ iterate (concatMap succ) [start]


Both functions generate the list of states reachable from a starting state in a finite number of steps. The inputs to bfs and dfs are the starting state and a “successors” function taking a state to the list of its “child” states.

What consistently impresses me about Haskell is that algorithms can be expressed in code as concisely as in English, if only you can learn the language to the same level of native fluency. As a native English speaker who’s only been writing Haskell casually for a year, I puzzled over the two one-liners in this post for about an hour before getting them right!

# Evolvability and Learning

This post investigates the paper Evolvability by computer scientist Leslie Valiant analyzing evolution and its limits through the lens of machine learning theory.

The first section gives an overview of Valiant’s now famous Probably Approximately Correct learning model, and the material is derived from Kearns and Vazirani’s short textbook Introduction to Computational Learning Theory. Valiant’s more recent notion of evolvability (explored in the second section) implies PAC learnability, but not conversely. In particular, the parity functions (i.e. the mod 2 linear functions ${\{0,1\}^n\rightarrow\{0,1\}}$) are learnable, but provably not evolvable (under Valiant’s or any similar notion of evolvability).

Throughout, I’ve included some fun pictures, produced by simple simulations in Python with matplotlib.

# Making change

Consider the classic problem: How many ways can one make change for one dollar using half-dollars, quarters, dimes, nickels, and pennies? Or more generally, how many ways can one make change for a given amount using arbitrary (positive integer) denominations?

This post chronicles a series of incremental improvements to solutions to this problem. In the first section, we attack the problem with dynamic programming in Python, and we’re able to count the ways to change quite large amounts of money (eventually up to about \$100M for the given set of five coins). The second section explores a nice method for deriving closed form solutions, due to Lee Newberg, and the third is a synthesis of the previous two, automating the closed form derivation in the general setting.

# What is a programming language?

This post is my highly condensed take on Abelson and Sussman’s classic Structure and Interpretation of Computer Programs (SICP) and Krishnamurthi’s Programming Languages: Application and Interpretation (PLAI), which I think do a nice (if incomplete) job of answering the question “what is a programming language?” by implementing several of them.

Just as in the reference texts, the example languages I’ll give are fragments of Lisp, implemented in Racket (a dialect of Lisp in the Scheme family). Lisp syntax is unusual in that it forces the programmer to explicitly write out parse trees for code, e.g. (+ 2 (* 3 4)) instead of 2 + 3 * 4.

The benefit of this is that I don’t have to write a parser just to experiment with languages: code written in Lisp-like syntax can be read literally as a data structure with the Lisp builtin quote (usually abbreviated with a single tick mark ').

My goal in this post is to implement a programming language which can run the following two test programs with minimal syntactic revision.

The first test is a recursively defined factorial function; that is, I want our language to support recursion.

(define (fact n)
(if (= n 0)
1
(* n (fact (- n 1)))))


The second test is Paul Graham’s accumulator function, specified in the appendix to his article Revenge of the Nerds. Graham thinks a good test of a language’s expressiveness is the length of its shortest accumulator implementation, and who am I to argue with him? The idea of an accumulator: one calls (make-accumulator 100), assigning the result to a variable a; then a is a procedure, and evaluating (a 10) once gives 110, evaluating (a 10) again gives 120, and evaluating (a -34.1) at this point gives 85.9. Different accumulator objects produced by make-accumulator should be independent.

(define (make-accumulator n)
(lambda (x)
(begin (set! n (+ n x))
n)))


The above Racket implementation relies on the following three language features, all of which I intend to capture in the toy language of this post:

• Functions are first-class values: they are valid inputs to and return values from other functions.
• Mutable data: variable values can be reassigned after they’ve been defined.
• Lexical variables: I want the ability to both read and write to intermediate scopes.1

With our goal in mind, we start by defining a very simple little programming language which, while Turing complete, isn’t sufficiently powerful to easily do what we want.

# Sam and Polly and Python

The Sam and Polly Puzzle is a beautiful riddle in which two logicians Sam and Polly must simulate the other’s thought processes several layers deep, deriving information from seemingly unhelpful statements. While many variations have been proposed, I first heard of the puzzle from the excellent list at the XKCD wiki, where it takes the following form:

Sam and Polly are perfectly logical mathematicians. A student walks in and says: “I’m thinking of two numbers x and y, with 3 <= x <= y <= 97. I’ll tell their sum to Sam, and their product to Polly.” She does so, then leaves, and the following conversation takes place:

Sam (to Polly): You can’t know what x and y are.

Polly (to Sam): That was true, but now I know.

Sam (to Polly): Now I know too.

Find x and y.

If you haven’t solved this riddle or one of its variations before, I absolutely recommend giving it a try before reading on. It took me about three hours to solve, with a whiteboard and the Python programming language.

This post consists of:

• Section 1: A clean Python solution
• Section 2: An investigation of the (somewhat weak) dependence on the bounds 3 and 97
• Section 3: A discussion of unbounded variations of the riddle.

The most common variant on the puzzle (and the original version published by Freudenthal in 1969, available here) uses the following bounds instead: 2 <= x < y and x + y <= 100, leading to a different solution. I’m sticking with the above formulation just because that’s the version that I saw and started thinking about before looking around to see what was known. The solution in the following section can be easily modified to solve Freudenthal’s version.

This riddle also known as the Sum and Product Puzzle, or as the Impossible Puzzle (not to be confused with the Hardest Logic Puzzle Ever, another excellent riddle).

The focus of this post is the mathematics of monads, though there are plenty of code snippets in this post. I avoid the somewhat complex and opaque IO monad in this post, in favor of exploring simpler monads (especially List and Maybe) more completely.