Monads For The Terrified

It seems like everyone writes a monad tutorial in the Haskell community… Well, here’s mine.

People learning Haskell generally seem to get tripped up about monads. There are good reasons for this.

1. Monads are, really, needed to write a serious Haskell program. As a consequence, people generally try to learn them fairly shortly after beginning to use Haskell.
2. Monads are defined in Haskell and have a very short definition. As such, it is very tempting to not just teach someone how to use monads, but to also try to teach them the underlying definition. The definition involves a bunch of rather advanced Haskell. In combination with (1), this is a big problem.
3. Monads are a very abstract idea. I’m not really sure that the motivation can be properly grasped by anything other than using them.
4. Monads are generally interweaved with the idea of an IO object.

This introduction attempts to avoid some of these problems. In particular, it is only going to teach you how to use monads and not what they are. This avoids (2) and, to a lesser extent, (3). I’ve tested this approach on a number of people in the last few months, and it seems to be quite effective. That said, I understand that some people may prefer an introduction focusing on the what and why, in which case you may wish to look Chris Smith’s Why Do Monad’s Matter?.

Some day, you will need to learn more. But, if you find you understand the contents of this tutorial, I’d encourage you to wait and play around with monads for a while. Then, when the time comes to learn the in full, they’ll be natural and obvious ideas. We can talk more about that later. For now: onwards!

(Read more on github)

Advertisement

My Baby Kernel, My Baby Kernel….

(About the title: I heard a certain commercial as I was writing it and couldn’t resist… Why do people insist on having TVs loud enough that I can clearly here it from another room?)

Over the Summer I got curious about all that low level stuff again (I was the previous Summer as well, that led to me designing a simple processor — read glorified 8-bit calculator that couldn’t divide — on paper). Someone at hacklab.to pointed me towards some resources and soon I making a kernel.

I implemented output (write to the terminal) and a tiny bit of memory management (just give pointers to sections of memory, note which ones you gave, unnote them — nothing to avoid memory fragmentation). I never got around to input, but I had a lot of fun. Here’s a screenshot (yes I’m obssesed with making things colourful — I’ve even played around with syntax highlighted math!):

Good resources are available at osdev, if you’re interested.

Anonymous Functions in Math and CS

Consider:

This is how one normally declares a function in math: by describing what the value of the function applied to a variable would be. One consequence of this approach is that ir necessitates a variable name, in this case , being assigned to the function.

This may not sound significant or problematic, but consider what the parallel of this in a different class of objects, like numbers would be. Before doing anything, we’d have to assign a variable to the number! For example, we couldn’t just write , we’d have to write . This may still not seem significant. After all, it’s only functions; people only have to define them occasionally.

I’d like to mention a theory that someone (Kelly Rose, one of the leaders — read teachers — of hacklab.to‘s math reading group) mentioned to me recently, that the reason two people (Newton and Leibniz) effectively simultaneously discovered calculus after people failed to for however many thousand years was that notation had developed that allowed for the discovery. (Interesting side note: this individual suggested that category theory may be the next big change.)

If this is theory is correct (and I’m not sure how we could every be certain) then it is the best example I can think of, of something I’ve been thinking about for several weeks: the importance of notation. (I’m using the term `notation’ loosely as including something that isn’t truly a new idea but is a new way of presenting the idea.)

It seems obvious to me that if one makes an idea difficult to represent, a person will avoid using it (or make an easier way to represent it). In some ways, this is applying the Sapir-Whorf hypothesis to things other than spoken language: the medium (traditional language, visualisation, notation, etc) of thinking effects the thoughts themselves. (If you’ve been nodding along, consider the effects English must be having on you mind; you may now wish to look at Lojban.)

I believe this is true, to an extent that I am probably failing to convey. (It’s why, for example, I find it deeply troubling that isn’t defined as : think about all the students who would have had a better understanding of trigonometry and more respect for math in general if it wasn’t for the fact that Pi Is Wrong.)

But we’ve digressed. Back to functions. We need to ask, is there a way to avoid defining a variable when using functions. In fact there is: . For example, the following to statements are identical:

We call an anonymous function. Another notation for this is using lambda calculus. We represent a function with . For example, the earlier example would be .

This has endless usefullness in math. It can provide an ellegant way to represent the Mandelbrot set, for example:

Translation for non-mathematicians: the set of complex numbers such that if we square x, add x, square that and add x, and so on infinitely, we won’t end up with infinity.

We can also use this to define functions that return functions using it. For example, we can define the differential operator, :

We can also use anonymous functions in programing. For example, python allows us to use lambda calculus in it. The following is perfectly valid:

>>> (lambda x: x*x +3)(2)
7

Now, you may have noticed that we can do some really interesting things with this. And could do even more interesting things, if we could make recursive functions.

Some programing languages support anonymous recursive functions. For example, in javascript, functions are passed a `callee’ argument that allows one to recurse on itself. Thus, we can implement an anonymous function that gives us a term in the Fibonacci sequence.

(function (x) {
  if (x <= 2) {
    return 1;
  } else {
    return arguments.callee(x - 1) + arguments.callee(x - 2);
  }
})(6) // = 8

More on this is available here.

But what about in math? There doesn’t seem to be a well defined notation for anonymous recursive functions in math… So, I’ve had to invent my own.

In lambda calculus, I’ve always perceived the lambda to be a place holder for the function. So, I’m rather fond of the notation . If one uses that notation, it’s a small step to use a lambda on the other side of the the equals sign…

We can use this notation to do some very cool things. For example, we can use this to make the Cantor set:

Translation for non-mathematicians: Take the line segment from 0 to 1, remove the middle third, then remove the middle third from the remaining pieces, and so on infinitely.

Of course, this notation does run into problems when one wants to have nested lambda calculus, but this can be fixed by using subscripts, ie .

/dev/audio: Raw Audio

Most Linux users are familiar with /dev/audio. Writing to it plays audio and reading from it records it. It accepts raw audio.

Some popular tricks with it are:

cat /dev/urandom > /dev/audio #Play Random Noise
cat /dev/audio > soundrecording #Record audio to file.
cat soundrecording > /dev/audio #Play recorded file.

A more complex one is eavesdroping on a room with a remote computer.

cat /dev/audio | nc -lp $PORT #Remote Computer
nc $IPADDR $PORT > /dev/audio #Local Computer

Where $PORT is the port you wish to use and $IP is the address of the remote computer.

But can one make synthetic sounds? I couldn’t find any documentation on how /dev/audio represents information. After playing around with it, however, I have come up with a model that at the very least predicts it reasonably well.

It seems that every character represents a certain voltage being applied to the speaker. Each characters value is proportional to its integer representation. /dev/audio accepts approximately 6000 chars/s. Thus, we can create a C function like:

/** @param freq: The frequency in Hertz (s^-1)
  * @param amp:  The amplitude (ie. loudness), unit not defined. Within the range 0-256.
  * @param time: The length in seconds.
  * @return A string representing the sound. Write to /dev/audio to play.  */
string sound(double freq, double amp, double time) {
	double r = 6000; // The number of characters interpreted by the speaker per second.
	int n = (int) time*r;
	string ret;
	for (int i = 0; i < n; ++i){
		ret += (char) (sin(i*freq)*amp+128);
	}
	return ret;
}

It’s not perfect, but it works. In particular, the low sampling rate results in horrible sound quality. r is not quite right either…

Update: It has come to my attention that /dev/audio accepts .wav files. The resolution can be changed.