Monthly Archives: January 2007

Basics: Sets

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.

Continue reading

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.

Continue reading

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).

Continue reading

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.

Continue reading

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.

Continue reading

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.

Continue reading

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.

Continue reading

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.

Continue reading

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:

n. See {recursion}.

Continue reading

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.

Continue reading