Software! Math! Data! The blog of R. Sean Bowman
The blog of R. Sean Bowman

## An interesting identity in propositional logic

June 22 2016

In the course of working on some propositional logic/SAT applications, I came across an interesting identity I don’t think I knew of before. It seems related to all kinds of stuff, but I guess that’s not unusual for math… Anyhow, this particular identity made it very easy to transform some assertions I needed from disjunctive normal form to conjunctive normal form. It’s also beautiful on its own, so I thought I’d write it down.

## Reduction strategies for untyped lambda calculus

May 08 2016

I dig the lambda calculus, and there’s a special place in my heart for the untyped calculus because of Scott’s amazing semantic interpretation, denotational semantics, and all that awesome jazz. But I have a confession: I don’t know a lot about reduction strategies for terms in the untyped lambda calculus. I wanted to remedy that (at least to some extent…), and I accidentally stumbled on a cool language to do it in. Here’s what I learned.

## Amortized Vector Append

March 04 2016

The C++ standard says that `vector::push_back` should run in amortized constant time. With a simple implementation where the vector is stored as an array which doubles in size when needed and each element is copied on every doubling, does this satisfy the time complexity requirement?

## Simplicial Complexes from Data

February 11 2016

In a previous article, we saw how to compute the (zeroth) persistent homology of a filtered simplicial complex. But how do we obtain such a complex, anyway? Scientists and others who work with data often start with a bunch of points in a high dimensional space. What are some good ways to turn that information into a filtered simplicial complex we can compute the persistent homology from?

## Graph clustering, TILO, and interactive demos

February 09 2016

I’d like to introduce an algorithm for finding clusters in graphs. This is an important problem in machine learning, in part because so many problems can be phrased as finding “nice” clusters in a given graph, where the meaning of "nice" tends to depend on the particular application. It’s easy to imagine simple applications of a good clustering algorithm, like finding groups of friends in a social network. But things only get more interesting from there.

## Kleisli triples, Monads, and Computing

February 01 2016

We learned about monoids, we learned the (mathematician’s) definition of a Monad, and now we’re going to take a look at at least one alternative (but equivalent) definition more often used in computer science. This is the Kleisli triple.

January 04 2016

We previously looked at a generalization of the familiar algebraic concept of a monoid to a category. We’re now in a position to give the “mathematician’s definition” of a monad. People seem to have different opinions of this definition. I personally think that it’s simple, elegant, and captures the spirit of generality of category theory. I have heard that some people use this definition to belittle or confuse people. Perhaps it’s just that people feel belittled or confused by it. In any case, describing a monad isn’t easy, and we shouldn’t feel bad if we don’t understand it very well at first.

December 01 2015

I want to talk about monads. These are fairly obscure mathematical objects that have received quite a bit of attention in the programming community lately. This, I think, is mostly because of their use in Haskell to handle "side effects" and other notions of computation inside the type system. It’s grown from there, however, and now you can find monad tutorials and code using monads in languages from Javascript to C++. Today, I want to talk a little about category theory, the history of monads, and the context in which mathematicians and theoretical computer scientists see them.

## Monoids and Categories

October 03 2015

At the risk of alienating those of you who are more interested in software than abstract mathematics, I’d like to write about some basic category theory. The idea is to work my way up to defining a monad, because that seems to be a requisite exercise for any programming language blogger. Here, I’d like to talk about something a bit simpler: monoids.

## Modules, Barcodes, and Applications

September 18 2015

I’d love to write more about persistent homology, and eventually I’ll get around to it, but right now I wanted to talk about some math that undergraduate math majors who know a little algebra can understand. Although this is prerequisite stuff for really understanding persistent homology, you’ll certainly be able to understand the basics of persistent homology without understaing this. You might not ever decide to, but you could also come back later, after you’ve learned a bit about persistent homology, to get an idea of how the details work. (I should mention that this stuff is worth studying because it’s cool in its own right, and one reason I’m writing it is as an opportunity for me to try to remember some of it!)

## The Quoteboard

September 16 2015

I have lots of heros and role models: mathematicians, compter scientists, academics, practicioners, articulate polymaths, and even a politician or two. Here I’ve collected some quotes I like. I’ll periodicaly add to them if I can remember to.