Blog

Functor, Applicative, Monad Part 3

There may have been some misconceptions due to the way I started this series in part one. The concept of monads is not the key to performing IO in a purely functional way, they are what makes it practical. IO in Haskell is performed by the IO System, which performs one big IO Action (Main.main) when the Program is run. This IO Action is build up of smaller IO Actions, much like a pure function can be build out of smaller functions. IO Actions are represented by the IO Type.

A value of type IO a is an IO Action that, when performed, does some IO and returns a value of type a. The IO type is completely abstract, so there is no way to create a value of type IO a in pure code. You have to build it out of other values by using the power of monads.

getChar :: IO Char
putChar :: Char -> IO ()

These are two very basic functions: getChar is an IO Action that, when performed, does some IO and returns a Char (e. g. reading from stdin) and putChar takes a Char, returns an IO Action that, when performed, does some IO with the char (e. g. writing it to stdout) and returns () (unit). An IO action is just a value in the Haskell Typesystem so we can pass it around from function to function in a purely functional way. The only way to actually perform an IO action is to bind it to Main.main. 

module Main where

main :: IO ()
main = getChar >>= putChar

We use (>>=) to build one big IO Action out of two smaller ones exactly like we did in the State Monad. In fact, you can think of the IO Monad as a State Monad which passes around the state of the realworld.

What are the benefits of this approach to IO?

  1.  We don't loose the great modularity that functional programming gives us. We build IO Actions out of small parts, pass them around and bind one big IO Action representing the application that we want to write to main to perform it when the program is run.
  2.  The Typesystem makes it impossible to have sideeffects ruin our pure code. IO Actions are values that represent nonpure computations. Functions like getChar and putChar return IO Actions, they are not themselves IO Actions. They are pure functions because they return always the same IO Action (given the same arguments). This IO Action may give different results depending on the context they are performed in.

This is a rather brief explanation of the IO Monad but I think it is enough to get the point. There are a lot of much more detail explanations if you are interested.

Functor, Applicative, Monad Part 2

Monads

Monads are the next step on our way to understand how purely functional languages can perform IO. Here is the Monad typeclass:

class Monad m where
  return :: a -> m a
  (>>=) :: m a -> (a -> m b) -> m b

The function return in the Monad typeclass does exactly the same as pure in the Applicative typeclass. The function (>>=) (pronounced "bind") is more interesting. It takes a value wrapped in the Monad and a function, that does something to that value and wraps it in the same Monad. Again we are going to look at Maybe, which is also a Monad.

(Just 3) >>= (\x -> Just (x + 3))
> (Just 6)

Again the functionality of (>>=) depends on the Monad you are using. Just like <*> the bind operator in the Maybe Monad short circuits the computation when the left side is Nothing

Nothing >>= (\x -> Just (x + 3))
> Nothing

The type of bind enables you to actually perform the check for nothing in between the function calls. Lets look at this lispy definition of Lists.

data LispyList = NIL | Cons a (LispyList a)

car :: LispyList a -> Maybe a
car NIL = Nothing
car (Cons x xs) = Just x

cdr :: LispyList a -> Maybe (LispyList a)
cdr NIL = Nothing
cdr (Cons x xs) = Just xs

If you want to combine the functions car and cdr to the in Lisp also available function cadr (which gives you the first of the rest of a list) you run into a problem. The argument type of car doesn't match the output type of cdr. You have to check whether the output is (Just list) or Nothing.

cadr :: LispyList a -> Maybe a
cadr l = let l' = cdr l in
           case l' of
             Nothing = Nothing
             Just xs = car xs

To get the first of the rest of the rest you have to check for Nothing twice:

caddr :: LispyList a -> Maybe a
caddr l = let l' = cdr l in
            case l' of
               Nothing = Nothing
               Just xs = let l'' = cdr xs in
                           case l'' of
                              Nothing = Nothing
                              Just ys = car ys

You get the point. The bind operator in the Maybe Monad does exactly that: check result of first function, if Just x apply function two to x. So you can write cadr like:

cadr l = cdr l >>= car

Note that you actually have to give the argument to the first function so it matches the type of (>>=). The next function follows from that:

caddr l = cdr l >>= cdr >>= car

The problem most people have with Monads is, in my experience, not a problem with Monads in general, but with a specific Monad. If you want a different view on Monads, Brian Beckman does a great job at explaining Monads in terms of Functions and Monoids in this video. 

The basics of Monads are clearly visible in the Maybe Monad but to understand the IO Monad, we have to look at a Monad that gives many people (including sometimes me) a lot of problems: the State Monad.

The State Monad

The State Monad lets you simulate mutable state in Haskell. Lets first take a look at the State type and its Monad instance.

newtype State s a = State { runstate :: s -> (a,s) }

instance Monad (State s) where
   return a = State $ \s -> (a,s)
   m >>= k = State $ \s -> let (a,s') = runstate m s in
                             runstate (k a) s'

In the State Monad you hold a function of type s -> (a,s). The typevariable s represents the type of the state, the typevariable a represents the actual returntype of the function. So a computation in the State Monad turns the current state into a possibly modified state and a result of any type. To better understand the (>>=) implementation we are going to look at an example.

type Stack = [Int]

type StackState a = State Stack a

push :: Int -> StackState ()
push a = State $ \as -> ((), a:as)

pop :: StackState Int
pop = State $ \(a:as) -> (a, as)

The state here is a list of Int's. We call that a Stack and implement the two functions on Stacks: push and pop. Push takes another Int and puts it in the Stack as the new top element. The function that does that (the lambda expression in the definition of push) still needs to return a pair of type (a,s). Because there is no sensible thing to return here we just return () (unit) and the second part is the new stack. The whole thing is then wrapped into the State constructor.

The definition of pop follows the same concept. The function takes the stack, returns the top element as the result and the stack without the top element as the new stack. Again the function needs to be wrapped in the State Monad.

To see how the combination of those functions work we have to untangle the implementation of (>>=). The m on the left side of (>>=) has type (m a). So in the State Monad it holds a function that takes the current State and returns a pair of type (a,s). So the sensible thing to do would be to extract that function and apply it to the current state. That is what happens in the let expression. We get a pair (a,s'). The right side of the (>>=) is a function of type (a -> m b). We just got a value of type a so we apply the function k to a to get out (m b), which is something with a function of type s -> (b,s) inside. This function is again extracted and applied to the new state s'. All of this has to be another function in the State Monad, so it is wrapped in the State constructor.

Now what can we do with this? For example we can remove the second element from the stack like so:

removeSecond :: StackState ()
removeSecond = pop >>= \x -> pop >> push x

The (>>) operator does the same as (>>=) but it ignores the returned value from the left side, so in this case the second element from the stack.

This is how you thread some piece of mutable state from one pure function to another. The implicit side effect of changing the stack when you pop an element of the stack is made explicit by actually returning the changed stack alongside the top element. The details of making sure that the next function gets the new state of the stack is hidden in the implementation of (>>=).

Brandon Simmons does a great job at explaining the State Monad in a bit more detail. I definitely recommend reading his blogpost here:  http://brandon.si/code/the-state-monad-a-tutorial-for-the-confused/

In the next post we will take a look at how this is used to perform IO in Haskell.

Functor, Applicative, Monad Part 1

Functional Programming

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.

Functors

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. 

Applicative

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.