Category Archives: combinatorics

Random binary trees with a size-limited critical Boltzmann sampler

Today I’d like to talk about generating random trees. First, some imports and such (this post is literate Haskell). > {-# LANGUAGE GeneralizedNewtypeDeriving #-} > > module BoltzmannTrees where > > import Control.Applicative > import Control.Arrow ((&&&)) > import Control.Lens … Continue reading

Posted in combinatorics, haskell, math, species | Tagged , , , , , | 7 Comments

And now, back to your regularly scheduled combinatorial species

I’ve already mentioned this to people here and there, but haven’t yet announced it publically, so here it is: Stephanie Weirich and I have been awarded a grant from the NSF to study the intersection of combinatorial species and (functional) … Continue reading

Posted in combinatorics, math, writing | Tagged , | 10 Comments

Unordered tuples and type algebra

At Hac Phi a few weekends ago (which, by the way, was awesome), Dan Doel told me about a certain curiosity in type algebra, and we ended up working out a bunch more details together with Gershom Bazerman, Scott Walck, … Continue reading

Posted in combinatorics | Tagged , , , , | 7 Comments

Counting linear lambda terms: choice and correspondence

In my last post, I showed how to write down polymorphic types with numbers of linear inhabitants given by products of factorials and Mersenne numbers, but left open the question of types with five linear inhabitants in particular, and whether … Continue reading

Posted in combinatorics | Tagged , , , , | 1 Comment

Counting linear lambda terms: Mersenne numbers

In a previous post I posed the challenge of coming up with polymorphic types admitting certain numbers of linear inhabitants. (If you didn’t see the previous post and want to puzzle over an interesting lambda-calculus based problem, stop reading now … Continue reading

Posted in combinatorics | 18 Comments

Counting linear lambda terms

Just a little something with which I’ve been idly occupying spare brain cycles lately… read on for an interesting puzzle. Warm up: counting lambda terms Consider a stripped-down version of Haskell’s type system with only natural numbers, polymorphism, functions, and … Continue reading

Posted in combinatorics | Tagged , , , , , | 10 Comments

Species subtraction made simple

> {-# OPTIONS_GHC -fno-warn-missing-methods #-} > module Virtual where > > import Control.Applicative > import Test.QuickCheck Yesterday on #haskell, augur asked me to explain how subtraction works for combinatorial species. (For an introduction to species, see my paper from the … Continue reading

Posted in combinatorics, haskell | Tagged , , , , , , , | 14 Comments

Species and Functors and Types, Oh My!

My paper on combinatorial species and the species library (an improved version of my previous ICFP submission) has been accepted to the 2010 Haskell Symposium! I look forward to seeing people in Baltimore in September, and in the meantime the … Continue reading

Posted in combinatorics, haskell, math, writing | Tagged , , , , , | 2 Comments

Functional pearl on combinatorial species

I’ve just submitted a Functional Pearl to ICFP explaining combinatorial species in a way that is (hopefully) accessible and interesting to functional programmers. You can read the draft here — as always, comments, suggestions, etc. are welcome (although it’s too … Continue reading

Posted in combinatorics, haskell, writing | Tagged , , | 3 Comments

How to solve this differential equation?

How would you solve the differential equation with the initial condition ? I know what the answer is supposed to be, but I don’t know how to directly solve it. In case you’re wondering, is the exponential generating function for … Continue reading

Posted in combinatorics, math | Tagged , , , , | 15 Comments