Sets are truly amazing things. In the history of mathematics, they’re

a remarkably recent invention – and yet, they’re now considered to be the

fundamental basis on which virtually all of mathematics is built. From simple things (like the natural numbers), to the most abstract and esoteric things (like algebras, or topologies, or categories), in modern math, they’re pretty much all understood

in terms of sets.

# Monthly Archives: January 2007

# The Theory of Monads and the Monad Laws

As promised, I’m finally going to get to the theory behind monads. As a quick review, the basic idea of the monad in Haskell is a hidden transition function – a monad is, basically, a state transition function.

The theory of monads comes from category theory. I’m going to assume you know a little bit about category theory – if you have trouble with it, go take a look at my introductory posts here.

# Basics: Syntax and Semantics

Another great basics topic, which came up in the comments from last fridays “logic” post, is the

difference between syntax and semantics. This is an important distinction, made in logic, math, and

computer science.

The short version of it is: syntax is what a language *looks like*; semantics is what

a language *means*. It’s basically the distinction between numerals (syntax) and

numbers (semantics).

# More Monads: Stateful Programming

Time for more monads. In this article, I’m going to show you how to implement a very simple

*state monad* – it’s a trivial monad which allows you to use a mutable state

consisting of a single integer. Then we’ll expand it to allow a more interesting

notion of state.

# Twisted Spaces: Fiber Bundles

It’s been a while since I’ve written a topology post. Rest assured – there’s plenty more topology to come. For instance, today, I’m going to talk about something called a *fiber bundle*. I like to say that a fiber bundle is a cross between a product and a manifold. (There’s a bit of a geeky pun in there, but it’s too pathetic to explain.)

The idea of a fiber bundle is very similar to the idea of a manifold. Remember, a manifold is a topological space where every point is inside of a neighborhood that *appears* to be euclidean, but the space as a whole may be very *non-*euclidean. There are all sorts of interesting things that you can do in a manifold because of that property of being *locally* almost-euclidean – things like calculus.

A fiber bundle is based on a similar sort of idea: a *local* property that does *not* necessarily hold globally – but instead the local property being a property of individual points, it’s based on a property of *regions* of the space.

So what is a fiber bundle, and why should we care? It’s something that looks *almost* like a product of two topological spaces. The space can be divided into regions, each of which is a small piece of a product space – but the space as a whole may be twisted in all sorts of ways that would be impossible for a true product space.

# Basics: Logic, aka "It's illogical to call Mr. Spock logical"

This is another great basics topic, and it’s also one of my pet peeves. In general, I’m a big science fiction fan, and I grew up in a house where every saturday at 6pm, we all gathered in front of the TV to watch Star Trek. But one thing which Star Trek contributed to our vocabulary, for which I will never forgive Gene Rodenberry, is “Logic”. As in, Mr. Spock saying “But that would not be logical.”.

The reason that this bugs me so much is because it’s taught a huge number of people that “logical” means the same thing as “reasonable”. Almost *every* time I hear anyone say that something is logical, they *don’t* mean that it’s logical – in fact, they mean something almost exactly opposite – that it seems correct based on intuition and common sense.

If you’re being strict about the definition, then saying that something is logical by itself is an almost meaningless statement. Because what it means for some statement to be “logical” is really that that statement is inferable from a set of axioms in some formal reasoning system. If you don’t know *what* formal system, and you don’t know *what* axioms, then the statement that something is logical is absolutely meaningless. And even if you *do* know what system and what axioms you’re talking about, the things that people often call “logical” are *not* things that are actually inferable from the axioms.

# A Pathological Challenge: Prime Programming in NULL

Todays pathological language is actually in the form of a challenge for you. (Isn’t that

exciting?) It’s a very clever numerical programming language in the vein of Conway’s Fractran,

called NULL. The author of NULL describes it

as a reaction to 2 and 3 dimensional languages in the Befunge tradition; NULL is a *0*

dimensional language – a program is just a single point. It’s quite clever in its way; the only

problem is that is that there’s only *one* example program written in it. So the challenge is

to see if you can actually come up with some implementations of interesting programs.

# Basics: Correlation

Correlation and Causation

Yet another of the most abused mathematical concepts is the concept of *correlation*, along with the related (but different) concept of *causation*.

Correlation is actually a remarkably simple concept, which makes it all the more frustrating

to see the nonsense constantly spewed in talking about it. Correlation is a *linear relationship* between two random variables.

# Basics: Recursion and Induction

Time for another sort-of advanced basic. I used some recursive definitions in my explanation

of natural numbers and integers. Recursion is a very fundamental concept, but one which many people have a very hard time wrapping their head around. So it’s worth taking the time to look at it, and see what it means and how it works.

The cleverest definition that I’ve seen of recursion comes from the Hackers dictionary. In there, it has:

recursionn. See {recursion}.

# Haskell: A First Step Into Monads

The biggest nightmare for most people learning Haskell is *monads*. Monads are the

key to how you can implement IO, state, parallelism, and sequencing (among numerous other things) in Haskell. The trick is wrapping your head around them.