Monads: Are they wierd or just different? opened up todays discussion and introduction of monads which was lead by John Colley.

Although this was mainly about Monads, it was also presented the exercise which was missing from last week:

module BinaryTree
    where
      import Data.Maybe

      data BTree a = Leaf a
                   | Branch (BTree a) a (BTree a)

      findAllPath :: (a -> Bool) -> (BTree a) -> [[a]]
      findAllPath pred = g where
          g (Leaf l) | pred l = [[l]]
          g (Branch lf r rt) | pred r = map (r:) $ (findAllPath pred lf) ++ (findAllPath pred rt)
          g _  = []

Needless to say that the last meeting find(All)Path resembled nothing like good Haskell code. I think this one is nearer the goal. And this one, definitely seems to do it truly lazily, i.e., if you just ask for the head of the resulting list, nothing else should be computed. Now, why the other is different, I don’t know.

To do this experimentation, I tried to define:

genTree1 :: Int -> (BTree Int)
genTree1 0 = Leaf 1
genTree1 n = Branch (genTree1 (n-1)) 1 (genTree1 (n-1))

Needless to say, this will generate a tree with 1’s at the nodes and leafs with n levels.

You try (GHCi 6.6.1):

*BinaryTree> :set +s
*BinaryTree> head $ findAllPath (\x -> True) (genTree1 100000)
[1,1,1,1,1...]
(1.56 secs, 210968808 bytes)

Now, with the version from meeting 6:

*BinaryTree> :set +s
*BinaryTree> head $ fromJust $ findAllPath (\x -> True) (genTree1 100000)
*** Exception: stack overflow

Other values, like 10000, 100 or even 50 take a huge amount of time. Why?

The next part of the session (most of it) dealt with understanding monads. John Colley prepared some code for us to study and discuss. Here it is:

-- Variations on an Evaluator
--
-- Derived from
--   [1] Bird R., Introduction to Functional Programming using
--                Haskell, 2nd Ed 1988
--   [2] Wadler P., Monads for Functional Programming, Lecture
--                  Notes In Computer Science; Vol. 925, 1995
--   [3] Hudak P., Peterson J., A Gentle Introduction to
--                              Haskell 98, 1999

module Eval where

-- An evaluator that acts on simple terms
-- Either a term is a constant integer or a quotient "Div t u"
-- where t and u are terms

data Term = Con Int | Div Term Term

eval :: Term -> Int
eval (Con a) = a
eval (Div t u) = eval t `div` eval u

-- Some data
answer,evalerror :: Term
answer = (Div (Div (Con 1972) (Con 2)) (Con 23))
evalerror = (Div (Con 1) (Con 0))

-- *Eval> eval answer
-- 42
-- *Eval> eval evalerror
-- *** Exception: divide by zero

-- Note that GHC raises an exception - in the above references
-- this must be done by the programmer

-- Now we want to count the number of evaluations of `div`
-- but we can't just have a global variable as in other
-- programmming languages,
-- so introduce a type to represent computations that act
-- on state: a "state transformer"

newtype St a = MkSt (State -> (a, State ))
type State = Int

-- Introduce an auxiliary function "apply" that applies a
-- state transformer to a state, giving a value/state pair

apply            :: St a -> State -> (a,State)
apply (MkSt f) s  = f s

-- Now eval must (tediously) be re-written

seval          :: Term -> St Int
seval (Con x)   = MkSt f
                  where f s = (x, s)
seval (Div t u) = MkSt f
                  where
                  f s = (x `div` y, s'' + 1)
                        where
                        (x,s') = apply (seval t) s
                        (y,s'') = apply (seval u) s'

-- (Note Bird's use of s' and s'' to represent the state values)

 -- and we also need to specify how the state transformer is
 -- to be displayed

instance Show a => Show (St a) where
          show f = "value: " ++ show x ++ ", count: " ++ show s
                   where (x,s) = apply f 0

-- *Eval> seval answer
-- value: 42, count: 2
-- *Eval> seval evalerror
-- value: *** Exception: divide by zero

-- Now rewrite the the original evaluator to use a monad

meval           :: Monad m => Term -> m Int
meval (Con x)    = return x
meval (Div t u)  = do x <- meval t
                      y <- meval u
                      return (x `div` y)

-- "meval" takes a term and performs a 'computation' m,
-- yielding an integer

-- In the state monad, a computation accepts an initial state and
-- returns a value paired with the final state

instance Monad St where
         return x = MkSt f
                    where f s = (x,s)

         p >>= q  = MkSt f
                    where
                    f s = apply (q x) s'
                          where (x, s') = apply p s

-- define an operation to increment the state

tick  :: St ()
tick   = MkSt f
         where f s = ((),s + 1)

-- and now it is only necessary to make a small local change
-- to meval to add a call to "tick"

mevalSt          :: Term -> St Int
mevalSt (Con x)   = return x
mevalSt (Div t u) = do x <- mevalSt t
                       y <- mevalSt u
                       tick
                       return (x `div` y)

-- *Eval> mevalSt answer
-- value: 42, count: 2
-- *Eval> mevalSt evalerror
-- value: *** Exception: divide by zero

Most of the discussion went through by looking at the code and Haskell 98 tutorial ([3] of the code above).
We have also managed to convert mevalSt main body to its monad look:

(mevalSt t) >>= (\x ->
                     ((mevalSt u) >>= (\y ->
                                           (tick >>= (\_ ->
                                                          return (x `div` y))))))

And so it ended this meeting. Next meeting we keep on with monads.
However, to end I asked the participants a quick quote about monads. Here’s what I got:

“Where do you find the monad in the Monad?”
— Ross Horne

“Writing Haskell in the monadic style promises better extensibility, but using the monadic meta-language takes you back into the old world of sequential programming – there must be more to this than meets the eye…”
— John Colley

“Monads seems one of those concepts which you have to mess with long enough (without panicking) until you internalise what they really do and mean.”
— Paulo Matos