Functional Programming is programming with functions. So much so obvious. But if the only thing you can do is creating and applying pure (side effect free) functions to jet more functions, how can you actually write useful programs? In imperative languages like C, every statement you write, changes the state of the program and often the state of the real world. So performing IO, which is nothing short of changing the state of the real world, is trivial.
How can functional languages do this. One possibility is to allow some functions to perform side effects. This is the approach of languages like Lisp. Another approach is to keep the language itself free of side effects, and outsource side effects into the type system. To make this practical, there needs to be mechanism to combine small effectfull computations into larger ones and eventually into whole applications that perform actual work. The mechanism that languages like Haskell use is Monads, a concept from category theory. In this series of posts I'll try to explain what monads are, how to use them in your code and how they solve the IO problem.
When you implement a data structure like lists or trees in Haskell, you might want to consider making that structure an instance of the typeclass functor. A functor is basically something you can map over. Lispers know about the map functions (mapcar, mapcan, maplist, ...) that allow you to apply a function to every element in a list. In Haskell this concept works for every data structure that is a functor. Lets look at this implementation of a binary tree and its functor instance:
data Tree a = Leaf a | Node (Tree a) a (Tree a) class Functor f where fmap :: (a -> b) -> f a -> f b instance Functor Tree where fmap f (Leaf x) = Leaf (f x) fmap f (Node left x right) = Node (fmap f left) (f x) (fmap f right)
A tree of type a is either a leaf holding a value of type a or a Node with a left and right child tree of type a and a value of type a in the middle. The only function required to make any data structure a functor is fmap. fmap will apply the function f to all the values in the tree but will never change the structure of the tree itself.
An applicative functor is a functor, that ,while holding functions, can be directly applied to data. The applicative typeclass defines two functions: pure and <*>.
class Functor f => Applicative f where pure :: a -> f a <*> :: f (a -> b) -> f a -> f b
An example for an applicative functor is Maybe. The function pure wraps a value in the minimum context of the functor, that still holds that value. So (pure 3) in the Maybe applicative functor will give you (Just 3). If you have a function wrapped in a Maybe, for example (Just (+ 3)), you can directly apply that function to a value wrapped in a Maybe.
(Just (+ 3)) <*> (Just 3) > (Just 6)
The great thing about this is, that the functionality of <*> depends on the Functor you are using. In the Maybe functor it short circuits the computation as soon as the function itself or the value the function is applied to is Nothing.
Nothing <*> (Just 3) > Nothing (Just (+ 3)) <*> Nothing > Nothing
You can also use <*> in sequence:
pure (+) <*> (Just 3) <*> (Just 3) > (Just 6)
The pure (+) <*> (Just 3) evaluates to the partially applied function (+ 3) wrapped in a Just. This function is then applied to (Just 3) to give the result (Just 6)
Monads go one step further, but this is a story for the next post.