Saturday, January 19, 2008

(Haskell) Monads for Imperative Peeps

Warning, since I am still learning Monads, it's quite possible the following is partially or even entirely wrong.

Why Monads

Functional programming languages have the constraint that their functions cannot have any side-effects. A function cannot do anything except produce a return value which is strictly dependent on its input values.

This is done for many good reasons. One such reason is to allow allowing some pretty mean performance optimizations: specifically allowing each individual "pure" function to run on their own processor core, since by definition each function is dependent on its input only, and can run efficiently this way.

However this constraint effectively eliminates entire sub-sets of useful and essential operations. Most notably IO operations such as printing or reading from the console.

A monad is a abstract idea that allows functional languages to stay theoretically coherent by encapsulating side-effect producing operations within themselves. Monadic functions can then be separated from the remaining pure functions when optimizing.

Monads are also extremely useful for encapsulating entire classes of behavior by type. For example a monad for functions that print or read from an OS provided data source is called IO. For functions that print or read strings from the console, the embedded type for IO would be String, and thus their type would be String -> IO String.

What are Monads

In programming languages, monads are meta-types that embed other types.

A monad has 3 parts:
1. A type construction, which defines how to embed a type in the monad
2. A unit function, which explains how to place a value of a type into a value of the monad, "as is"
3. A binding operation, which explains how pull out a value of a type from the monad, apply a pure function to it, and return the result to the monad

As an example we will construct a monad called Maybe that defines a type who's values are either invalid, or from a valid range:

1. data Maybe t = Just t | Nothing

Which says that the monadic type Maybe with parameter type t is a type who's values are of type "Just t" or "Nothing". Nothing is the type of invalid values.

2. return x = Just x

Which defines a function that wraps any value in the identity type Just, and thus embeds it the monad Maybe by our definition in 1.

3. (Just x) >>= f = f x
Nothing >>= f = Nothing

Which says that any function f can be applied to the type Just x as a normal, every-day function call; but any value of the Nothing type always yields Nothing. This means that whenever an invalid value is encountered, all functions from that point on are also invalid.

No comments: