Category Archives: math

Parametricity for Bifunctor

I’ve begun work to add Bifunctor, Bifoldable, and Bitraversable to the Typeclassopedia. While thinking and writing about Bifunctor I ended up proving some “folklore” results for my own satisfaction, and decided someone might possibly find it useful if I formally … Continue reading

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

Sum of heights in a binary tree

Executive summary: every year when teaching data structures I always forget how to analyze the cost of building a binary heap, which amounts to summing the heights of all the nodes in a full binary tree. So I’m writing down … Continue reading

Posted in math, teaching | Tagged , , , , , , , | 1 Comment

Signed sets and ballots and naturality

This is blog post #3 in a series on signed sets and ballots (the previous posts are here and here). Naturality, isomorphism, and equipotence When are two species isomorphic? Since species are, by definition, functors , the obvious answer is … Continue reading

Posted in combinatorics, math, species | Tagged , , , , , , , | 2 Comments

Signed sets and ballots, part 2

Recall, from my previous post, that our goal is to find a combinatorial proof showing the correspondence between signed sets and signed ballots, where a signed set is just a set of elements, considered positive or negative according to the … Continue reading

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

Signed sets and ballots, part 1

The other day, Anders Claesson wrote a very nice blog post explaining a more combinatorial way to understand multiplicative inverses of virtual species (as opposed to the rather algebraic way I explained it in my previous post). In the middle … Continue reading

Posted in combinatorics, math, species | Tagged , , , , , , | 2 Comments

Any clues about this Newton iteration formula with Jacobian matrix?

A while ago I wrote about using Boltzmann sampling to generate random instances of algebraic data types, and mentioned that I have some code I inherited for doing the core computations. There is one part of the code that I … Continue reading

Posted in math | Tagged , , , , , , | 8 Comments

The network reliability problem and star semirings

In a previous post I defined the network reliability problem. Briefly, we are given a directed graph whose edges are labelled with probabilities, which we can think of as giving the likelihood of a message successfully traversing a link in … Continue reading

Posted in math | Tagged , , , , , | 9 Comments