BEGIN 16_12_08_ExamplesOfMonads.lhs

-##########################################################
I/O OPERATIONS, SIDE-EFFECTS, MONADS
-##########################################################

READING:
Simon Thompson's books, Sections 18.7, 18.8 and 18.9] -- 
go lightly, this material is not easy to understand.

-##########################################################

We import module Hugs.IO which contains IO operations beyond those
in Prelude.hs:

>  module Main where
>  import Hugs.IO

We can use the "do" construct in Haskell, although it
is syntactic sugar for a purely functional style of writing code (based on
the "Monad" class). We used the "do" construct because it is friendly and
resembles the sequencing of imperative actions in languages such as C, C++
and Java -- though there are important differences.

In this handout, we explain how the "do" construct can be de-sugared.
Before we do this, we review how to write do-sequences of IO actions
by way of examples.

-###########################################################

HOW TO WRITE do-SEQUENCES OF I/O ACTIONS

Once more, here are some IO operations with their types -- these are in the
library:

   getChar :: IO Char
   putChar :: Char -> IO ()
   putStr  :: String -> IO ()
   print   :: Show a => a -> IO ()
   getLine :: IO String
   isEOF   :: IO Bool
   return  :: a -> IO a

The "do" construct takes one or more expressions, each of type "IO t"
for some type "t" (not necessarily the same "t" for all the
expressions). For example -- don't worry about what the program does,
just make sure you know that it is a valid Haskell program:

>  e1 = do
>       getChar
>       getLine
>       return True
>       return 3
>       isEOF

Suppose M is an expression such that "M :: IO t" for some type t. Then we
can place M on the right-hand side of assignment symbol "<-" as in:

   x <- M

And the type of the variable of the variable "x" on the left-hand side
is exactly "t" (not "IO t"). We can insert expressions of the form "x <- M"
in a do-sequence, provided the last expression in the sequence is NOT of 
this form.

For another example -- again don't worry about what the program does:

>  e2 = do
>       x <- putChar 'a'
>       y <- putStr " abc "
>       isEOF

Or for another meaningless program:

>  e3 = do
>       x <- putChar 'a'    -- what is the type of x
>       y <- putStr  " b "    -- what is the type of y
>       if (x == y) then putStr " YES " else putStr " NO "
>       isEOF

Here are simple and more meaningful examples of how these operations
can be used. 

>  f1 = do                 -- f1 :: IO ()
>     print "Hello"        -- print :: Show a => a -> IO ()
>     let x = 3            -- this is a different use of "let", which allows
>                          -- to make a local declaration in a do-sequence,
>                          -- note in particular the absence of keyword "in"
>     let x = 2; y = 3; z = 4
>     print "The answer is"
>     print (x*y*z)

>  f2 = do                   -- f2 :: IO ()
>     print "Hello"
>     x <- getLine           -- getLine :: IO String, x :: String
>     print "The input is"
>     print x

>  get2lines = do           -- get2lines :: IO (String,String)
>     line1 <- getLine      -- getLine :: IO String, 
>     line2 <- getLine      -- line1, line2 :: String
>     return (line1,line2)  -- return :: (String,String) -> IO (String,String)

>  get2lines' = do         
>     line1 <- getLine     
>     line2 <- getLine     
>     x <- return (line1,line2) 
>     print x

>  f3 = do                   -- f3 :: IO ()
>     (x,y) <- get2lines     -- get2lines :: IO (String,String)
>     print ("You typed " ++ x ++ " then " ++ y ++ ".")

A few things to note:

(1) Keyword "do" introduces a sequence of IO actions 
    -- as in "f1", "f2" and "f3".

(2) You can insert a local declaration between IO actions in a do-sequence,
    in order to name an expression, using the keyword "let". But note this
    "let" is different from the "let-in" used in expressions
    -- as in "f1".

(3) To return a value from a do-sequence, use the library function "return". 
    Note that this value is NOT returned to the standard output (i.e. the 
    screen), and it is lost if not used elsewhere
    -- as in "get2lines".

(4) You can insert an "assignment" using the keyword "<-" in order to
    name the effect of an IO action
    -- as in "f2", "get2lines" and"f3".

(5) The type of a do-sequence of IO actions is the type of the last IO
    action in the sequence.

-####################################################################

SEVERAL EASY QUESTIONS -- EXPLANATION OF THE ANSWERS IS LEFT TO YOU.

Which of the following programs will cause an error:

>  f x = do
>      return [x,x]
>  f4  = do
>      x <- f 10
>      print x

f4 causes no error.

> {-
>  f5 = do
>     print (getLine)
> -}

f5 causes an error.

>  f6  = do
>      x <- return 1
>      print x

f6 causes no error.

> {-
>  f7  = do
>      x <- getLine
>      if x == "abc" then 
>                         print "x == abc"
>                         print "Cool!"
>                    else 
>                         print "x /= abc"
>                         print "Not cool!"
>  -}

f7 causes an error.

>  f8  = do
>      x <- getLine
>      if x == "abc" then do
>                         print "x == abc"
>                         print "Cool!"
>                    else do
>                         print "x /= abc"
>                         print "Not cool!"

f8 causes no error.

> {-
>  f9  = do
>      x <- getLine
>      if x == 1 then do
>                     print "x == 1"
>                     print "Cool!"
>                else do
>                     print "x /= 1"
>                         print "Not cool!"
> -}

f9 causes an error.

>  f10 = do
>      x <- getLine
>      if (read x) == 1 
>                then do
>                     print "x == 1"
>                     print "Cool!"
>                else do
>                     print "x /= 1"
>                     print "Not cool!"

f10 causes no error.

-###################################################################

We repeat the signature of the Monad class (copied from Prelude.hs):

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

To make our explanation concrete, and relate it back to the examples
above -- as well as to the examples in Appendix 19 -- you can think of
the type constructor "IO" as an instance of the class "Monad" -- which
requires a declaration of the form:

   instance Monad IO where
      (>>=)  f g =  ...
      return x   =  ...
      (>>)   f g =  ...
      fail       =  ...

and, indeed, there is a declaration of the preceding form in Prelude.hs (or
equivalent to it). So, whenever we use the parameter "m" below, you can think
that it stands for "IO".

For sequencing input-ouput operations, or other similar imperative actions,
the two important functions are (>>=) and (>>). In fact, the second (>>)
can be defined in terms of the first (>>=), as we show shortly. First
recall, how (>>=) works:

     It takes an input-output action "f :: IO a" as first argument, 
     then takes a function "g :: a -> IO b" as second argument, 
     then passes the effect of "f" (something of type "a") to "g",
     which finally returns an input-output action of type "IO b".

Now, for the definition of (>>) in terms of (>>=):

    (>>)     ::  m a -> m b -> m b
    (>>) f g  =  (>>=) f (\ _ -> g)

Note carefully how (>>) works: It acts like (>>=) except that the
effect of the first argument "f" is discarded rather than being passed
to the second argument "g".

-##########################################################

SYSTEMATIC DE-SUGARING OF "do" SEQUENCES

There are 4 rules -- where 
   <e> stands for a single IO action, 
   <es> stands for a sequence of IO actions, 
   <decls> stands for a sequence of bindings (using "let" or "let-in"),
   ":=:" stands for "is de-sugared to"

(A)   do { <e> }               :=:  e  

(B)   do { <e> ; <es> }        :=:  <e> >> do { <es> }

(C)   do {let <decls>; <es> }  :=:  let <decls'> in do { <es> }
      
      where <decls'> is obtained from <decls> by eliminating multiple
      bindings (read from right to left). <decls> can be mutually 
      recursive declarations.

(D)   do { x <- <e> ; <es> }   :=:  <e>  >>=  (\ x -> do { <es> })

Rule (A) says that when performing a single IO action, the "do" can be
eliminated.

Rule (B) says that to execute "do { <e> ; <es> }", we first execute the
IO action <e>, throw away its effect, and then execute "do { <es> }".

Rule (C) explains how to lift let-declarations out of a do-declaration.

Rule (D) explains how to eliminate an assignment that uses keyword "<-".

-#######################################################################

SEVERAL EXAMPLES

BEGIN EXAMPLE 1

Based on Rule (D), given a do-sequence of the form

     do  x_1 <-  <e_1>
         x_2 <-  <e_2>
         ...
         x_n <-  <e_n>
         return (f x_1 x_2 ... x_n)

we can de-sugar it as

     <e_1>  >>=  \ x_1 ->
     <e_2>  >>=  \ x_2 ->
      ...
     <e_n>  >>=  \ x_n ->
     return (f x_1 x_2 ... x_n)

END EXAMPLE 1

BEGIN EXAMPLE 2

The do-sequence denoted "f1" at the beginning of this handout, namely:

  f1 = do            
     print "Hello"   
     let x = 3                            
     let x = 2; y = 3; z = 4
     print "The answer is"
     print (x*y*z)

can be de-sugared as:

>  f1' = print "Hello"
>        >>
>        let x = 2; y = 3; z = 4 
>        in  print "The answer is"
>            >>
>            print (x*y*z)

END EXAMPLE 2

BEGIN EXAMPLE 3

The following do-sequence "f11":

>  f11 = do            
>     x <- getLine  
>     let fact x = if (x == 0) then 1 else x * fact (x-1) 
>     print ("The factorial of " ++ x ++ " is")
>     print (fact (read x :: Int))

can be de-sugared as:

>  f11' = getLine
>         >>= \ x ->
>             let fact x = if (x == 0) then 1 else x * fact (x-1)
>             in  print ("The factorial of " ++ x ++ " is")
>                 >>
>                 print (fact (read x :: Int))

END EXAMPLE 3

BEGIN EXAMPLE 4

The following do-sequence "f12":

>  f12 = do            
>     x <- getLine  
>     let even z = if (z == 0) then True else odd (z-1);
>         odd  z = if (z == 0) then False else even (z-1)           
>     if even (read x :: Int)  
>         then print ("The input number " ++ x ++ " is even")
>         else print ("The input number " ++ x ++ " is odd")
                 
can be de-sugared as:

>  f12' = (>>=)            
>         getLine  
>         (\ x -> let even z = if (z == 0) then True else odd (z-1);
>                     odd  z = if (z == 0) then False else even (z-1) 
>                 in  if even (read x :: Int)  
>                     then print ("The input number " ++ x ++ " is even")
>                     else print ("The input number " ++ x ++ " is odd")  
>         )

END EXAMPLE 4

END 16_12_08_ExamplesOfMonads.lhs