Haskell: The Craft of Functional Programming
	Simon Thompson
	(c) Addison-Wesley, 1999.

	Chapter 18

Programming with actions
^^^^^^^^^^^^^^^^^^^^^^^^

>	module Chapter18 where

>	import Prelude hiding (lookup)

>	import IO		-- for isEOF (see note below, aslo)

>	isEOF = hugsIsEOF	-- this should be commented out in later
>				-- versions; it is here because Hugs 1.4
>				-- doesn't support isEOF

The basics of input/output
^^^^^^^^^^^^^^^^^^^^^^^^^^

Reading input is done by getLine and getChar: see Prelude for details.

	getLine :: IO String
	getChar :: IO Char

Text strings are written using 
	
	putStr :: String -> IO ()
	putStrLn :: String -> IO ()

A hello, world program

>	helloWorld :: IO ()
>	helloWorld = putStr "Hello, World!"

Writing values in general

	print :: Show a => a -> IO ()


The do notation: a series of sequencing examples.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Put a string and newline.

	putStrLn :: String -> IO ()
	putStrLn str = do putStr str
	                  putStr "\n"

Put four times.

>	put4times :: String -> IO ()
>	put4times str 
>	  = do putStrLn str
>	       putStrLn str
>	       putStrLn str
>	       putStrLn str

Put n times

>	putNtimes :: Int -> String -> IO ()
>	putNtimes n str
>	  = if n <= 1 
>	       then putStrLn str
>	       else do putStrLn str
>	               putNtimes (n-1) str

Read two lines, then write a message.

>	read2lines :: IO ()
>	read2lines 
>	  = do getLine
>	       getLine
>	       putStrLn "Two lines read."

Read then write.

>	getNput :: IO ()
>	getNput = do line <- getLine
>	             putStrLn line

Read, process then write.

>	reverse2lines :: IO ()
>	reverse2lines
>	  = do line1 <- getLine
>	       line2 <- getLine
>	       putStrLn (reverse line2)
>	       putStrLn (reverse line1)

Last example redefined to use a local definition.

>	reverse2lines' :: IO ()
>	reverse2lines'
>	  = do line1 <- getLine
>	       line2 <- getLine
>	       let rev1 = reverse line1
>	       let rev2 = reverse line2
>	       putStrLn rev2
>	       putStrLn rev1

Reading an Int.

>	getInt :: IO Int
>	getInt = do line <- getLine
>	            return (read line :: Int) 


Iteration and recursion
^^^^^^^^^^^^^^^^^^^^^^^

A while loop.

>	while :: IO Bool -> IO () -> IO ()

>	while test action
>	  = do res <- test
>	       if res then do action
>	                      while test action
>	              else return ()

Copying input to output.

>	copyInputToOutput :: IO ()
>	copyInputToOutput
>	  = while (do res <- isEOF
>	              return (not res))
>	          (do line <- getLine
>	              putStrLn line)

An important example: refer to the text to see why it fails to work as
required. (The incorrect version is primed.)

>	goUntilEmpty' :: IO ()
>	goUntilEmpty'
>	 = do line <- getLine
>	      while (return (line /= []))
>	            (do putStrLn line
>	                line <- getLine
>	                return ())

The correct program: the key is to think recursively.

>	goUntilEmpty :: IO ()
>	goUntilEmpty
>	  = do line <- getLine
>	       if (line == [])
>	          then return () 
>	          else (do putStrLn line
>	                   goUntilEmpty)


Adding a sequence of integers

>	sumInts :: IO Int

>	sumInts
>	  = do n <- getInt
>	       if n==0 
>	          then return 0
>	          else (do m <- sumInts
>	                   return (n+m))

Addiing a sequence of integers, courteously.

>	sumInteract :: IO ()
>	sumInteract
>	  = do putStrLn "Enter integers one per line"
>	       putStrLn "These will be summed until zero is entered"
>	       sum <- sumInts
>	       putStr "The sum was "
>	       print sum



The calculator
^^^^^^^^^^^^^^

This is available separately.


Input and output as lazy lists
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Reverse all the lines in the input.

>	listIOprog :: String -> String

>	listIOprog = unlines . map reverse . lines



Monads for Functional Programming
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

The definition of the Monad class
	class Monad m where
	  (>>=)  :: m a -> (a -> m b) -> m b
	  return :: a -> m a
	  fail   :: String -> m a

Kelisli composition for monadic functions.

(>@>) :: Monad m => (a -> m b) ->
                    (b -> m c) ->
                    (a -> m c)

f >@> g = \ x -> (f x) >>= g


Some examples of monads
^^^^^^^^^^^^^^^^^^^^^^^

Some examples from the standard prelude.

The list monad

	instance Monad [] where
	  xs >>= f  = concat (map f xs)
	  return x  = [x]
	  zero      = []

The Maybe monad

	instance Monad Maybe where
	  (Just x) >>= k  =  k x
	  Nothing  >>= k  =  Nothing
	  return          =  Just

The identity monad

>	data Id a = Id a 

>	instance Monad Id where
>	  return         = Id
>	  (>>=) (Id x) f = f x

The parsing monad

	data SParse a b = SParse (Parse a b)

	instance Monad (SParse a) where
	  return x = SParse (succeed x)
	  zero     = SParse fail
	  (SParse pr) >>= f 
	    = SParse (\s -> concat [ sparse (f x) rest | (x,rest) <- pr st ])

	sparse :: SParse a b -> Parse a b
	sparse (SParse pr) = pr

A state monad (the state need not be a table; this example is designed
to support the example discussed below.)

>	type Table a = [a]

>	data State a b = State (Table a -> (Table a , b))

>	instance Monad (State a) where

>	  return x = State (\tab -> (tab,x))

>	  (State st) >>= f 
>	    = State (\tab -> let 
>	                     (newTab,y)    = st tab
>	                     (State trans) = f y 
>	                     in
>	                     trans newTab)


Example: Monadic computation over trees
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

A type of binary trees.

>	data Tree a = Nil | Node a (Tree a) (Tree a)

Summing a tree of integers

A direct solution:

>	sTree :: Tree Int -> Int

>	sTree Nil            = 0
>	sTree (Node n t1 t2) = n + sTree t1 + sTree t2

A monadic solution: first giving a value of type Id Int ...

>	sumTree :: Tree Int -> Id Int

>	sumTree Nil = return 0

>	sumTree (Node n t1 t2)
>	  = do num <- return n
>	       s1  <- sumTree t1
>	       s2  <- sumTree t2
>	       return (num + s1 + s2)

... then adapted to give an Int solution

>	sTree' :: Tree Int -> Int

>	sTree' = extract . sumTree

where the value is extracted from the Id monad thus:

>	extract :: Id a -> a
>	extract (Id x) = x


Using a state monad in a tree calculation
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

The top level function ...

>	numTree :: Eq a => Tree a -> Tree Int

... and the function which does all the work:

>	numberTree :: Eq a => Tree a -> State a (Tree Int)

Its structure mirrors exactly the structure of the earlier program to
sum the tree.

>	numberTree Nil = return Nil

>	numberTree (Node x t1 t2)
>	  = do num <- numberNode x
>	       nt1 <- numberTree t1
>	       nt2 <- numberTree t2
>	       return (Node num nt1 nt2)

The work of the algorithm is done node by node, hence the function

>	numberNode :: Eq a => a -> State a Int

>	numberNode x = State (nNode x)

>	nNode :: Eq a => a -> (Table a -> (Table a , Int))
>	nNode x table
>	  | elem x table        = (table      , lookup x table)
>	  | otherwise           = (table++[x] , length table)
 
Looking up a value in the table; will side-effect the table if the value
is not present.

>	lookup :: Eq a => a -> Table a -> Int

>	lookup = lookup 	-- dummy definition: 
>				-- exercise for the reader

Extracting a value froma state monad.

>	extractSt :: State a b -> b
>	extractSt (State st) = snd (st [])

The top-level function defined eventually.

>	numTree = extractSt . numberTree