Transcript Document

COSC 4P41 – Functional Programming
Programming with actions
Why is I/O an issue?
• I/O is a kind of side-effect. Example:
Suppose there is an operation
inputInt :: Int
-- reads an integer
inputDiff = inputInt – inputInt
inputInt should return two different values (depending on the users
input). Hence, its evaluation depends on the context where (or when) it
is executed  side-effect!!!
• The meaning of an expression relying on side-effects is no longer
determined by looking only at the meanings of its parts.
© M. Winter
9.1
COSC 4P41 – Functional Programming
Monadic I/O
• The Haskell type IO a is the type of I/O actions of type a, e.g., the
elements of a are somehow wrapped into an I/O container; the
monad IO.
• An expression of type IO a is a program which will do some I/O and
then return a value of type a.
• One way of looking at the I/O a types is that they provide a simple
imperative language for writing I/O programs on top of Haskell,
without compromising the functional model of Haskell.
• This approach is called the monadic approach. It is more general and
can be used to incorporate side-effect into a pure functional
programming language (without its problems).
© M. Winter
9.2
COSC 4P41 – Functional Programming
Reading input and writing output
getLine :: IO String
getChar :: IO Char
putStr :: String -> IO ()
print :: Show a => a -> IO ()
where () is the type containing exactly one element; the element ().
Remark:
In WinGHCi just those I/O actions of type IO () are actually printed to
the screen.
© M. Winter
9.3
COSC 4P41 – Functional Programming
The do notation
The do notation is a flexible mechanism. With respect to the monad IO
it supports two things:
• it is used to sequence I/O programs, and
• it is used to ‘capture’ the values returned by IO actions and so to pass
these values to actions which follow them in the program.
In general:
• it is used to sequence programs wrapped in monad, and
• it is used to unwrap the values returned by the monad and so to pass
these values to actions which follow them in the program.
© M. Winter
9.4
COSC 4P41 – Functional Programming
Examples
putStrLn :: String -> IO ()
putStrLn str = do putStr str
putStr ”\n”
read2lines :: IO ()
read2lines = do getLine
getLine
puStrLn ”Two lines read.”
getNput :: IO ()
getNput = do line <- getLine
putStrLn line
where line names the result of getLine (local variable).
© M. Winter
9.5
COSC 4P41 – Functional Programming
Examples (cont’d)
reverse2lines :: IO ()
reverse2lines = do line1 <line2 <let rev1
let rev2
putStrLn
putStrLn
getLine
getLine
= reverse line1
= reverse line2
rev1
rev2
getInt :: IO Int
getInt = do line <- getLine
return (read line :: Int)
where return :: a -> IO a packs an a value in the IO monad.
© M. Winter
9.6
COSC 4P41 – Functional Programming
Examples (cont’d)
Notice, that the following program is not type correct:
getInt = do line <- getLine
(read line :: Int)
Each component of a do construction has to be an element of IO a for a
type a.
while :: IO Bool -> IO () -> IO ()
while test action
= do res <- test
if res then do action
while test action
else return ()
© M. Winter
9.7
COSC 4P41 – Functional Programming
Examples (cont’d)
isEOF :: IO Bool
copyInputToOutput :: IO ()
copyInputToOutput
= while (do res <- isEOF
return (not res))
(do line <- getLine
putStrLn line)
© M. Winter
9.8
COSC 4P41 – Functional Programming
Examples (cont’d)
goUntilEmpty :: IO ()
goUntilEmpty
= do line <- getLine
if line == []
then return ()
else (do putStrLn line
goUntilEmpty)
does not work since variables
goUntilEmpty’ :: IO ()
cannot be updated.
goUntilEmpty’
= do line <- getLine
while (return (line /= []))
(do putStrLn line
here we create a new variable
line <- getLine
return ())
© M. Winter
9.9
COSC 4P41 – Functional Programming
Calculator example
data Expr = Lit Int | Var Var | Op Ops Expr Expr
data Ops = Add | Sub | Mul | Div | Mod
type Var = Char
initial :: Store
value
:: Store -> Var -> Int
update :: Store -> Var -> Int -> Store
data Command = Eval Expr | Assign Var Expr | Null
commLine :: String -> Command
eval :: Expr -> Store -> Int
© M. Winter
9.10
COSC 4P41 – Functional Programming
Calculator example (cont’d)
command :: Command -> Store -> (Int,Store)
command Null
st = (0 , st)
command (Eval e)
st = (eval e st , st)
command (Assign v e) st = (val , newSt)
where val
= eval e st
newSt = update st v val
calcStep :: Store -> IO Store
calcStep st
= do
line <- getLine
comm <- return (commLine line)
(val , newSt) <- return (command comm st)
print val
return newSt
© M. Winter
9.11
COSC 4P41 – Functional Programming
Calculator example (cont’d)
calcSteps :: Store -> IO ()
calcSteps st = while notEOF
(do newSt <- calcStep st
calcSteps newSt)
notEOF :: IO Bool
notEOF = do res <- isEOF
return (not res)
mainCalc :: IO ()
mainCalc = calcSteps initial
© M. Winter
9.12
COSC 4P41 – Functional Programming
Further I/O
• File I/O
– readFile :: FilePath -> IO String
– writeFile :: FilePath -> String -> IO ()
– appendFile :: FilePath -> String -> IO ()
• Errors
– ioError :: IOError -> IO a
– catch :: IO a -> (IOError -> IO a) -> IO a
where IOError is the system-dependent data type of I/O errors. More on
error handling (especially the type IOError) can be found in the
documentation for the I/O library IO.hs.
© M. Winter
9.13
COSC 4P41 – Functional Programming
Monads
IO is a type constructor, i.e., an operation on types. It maps a type a to the
type IO a of I/O action on a.
A characteristic of the I/O monad is that it allows to sequence operations.
do line <- getLine
putStrLn line
What is the type of such a combinator which sequences the operations:
(>>=) :: IO a -> (a -> IO b) -> IO b
or, more general, for an arbitrary type constructor m, a combinator
(>>=) :: m a -> (a -> m b) -> m b
© M. Winter
9.14
COSC 4P41 – Functional Programming
Monads (cont’d)
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
(>>)
:: m a -> m b -> m b
fail
:: String -> m a
m >> k = m >>= \_ -> k
fail s = error s
Requirements (informally):
• The operation return x should simply return the value x, without
any additional computational effect.
• The sequencing given by >>= should be irrelevant of the way that
expressions are bracketed.
• >> acts like >>=, except that the value returned by the first expression
is discarded rather than being passed to the second argument.
• The value fail s corresponds to a computation that fails, giving the
error message s.
© M. Winter
9.15
COSC 4P41 – Functional Programming
Rules for monads
(>@>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> mc)
f >@> g = \x -> (f x) >>= g
Rules that should be satisfied:
(M1)
return >@> f
= f
identity law (left)
(M2)
f >@> return
= f
identity law (right)
(M3)
(f >@> g) >@> h = f >@> (g >@> h) associativity
In terms of (>>=):
(M1)
(return x) >>= f
(M2)
m >>= return
(M3)
(m >>= f) >>= g
= f x
= m
= m >>= (\x -> (f x) >>= g)
In category theory (>@>) is called the Kleisli composition.
© M. Winter
9.16
COSC 4P41 – Functional Programming
The do notation revisited
The do notation can be used for arbitrary monads (not just for the I/O
monad). It just a shorthand for an expression build up from (>>=) and (>>).
Example:
do line <- getLine
putStrLn line
putStrLn ”That’s it.”
return 5
is translated to
getLine
>>= putStrLn
>> putStrLn ”That’s it.”
>> return 5
© M. Winter
9.17
COSC 4P41 – Functional Programming
Examples of monads
• Identity monad
– m a = a
– m >>= f = f m
– return = id
• I/O monad
• List monad
instance Monad [] where
xs >>= f = concat (map f xs)
return x = [x]
fail s
= []
• Maybe monad (Error monad)
instance Monad Maybe where
(Just x) >>= k = k x
Nothing >>= k = Nothing
return
= Just
fail s
= Nothing
© M. Winter
9.18
COSC 4P41 – Functional Programming
Examples of monads (cont’d)
• Parsing monad (Parsec – a useful parser combinator library)
– Import statement: import Text.ParserCombinators.Parsec
The type GenParser a state b
• is the type of parsers taking lists of a elements as input producing an
element of b.
• is implemented similar to the type Parser from Week 7.
• has a parameter state. This parameter can be used as an internal state
storing information during the parsing process.
• has an internal and hidden error state. This state is used to keep track
of errors that occurred during the parsing process.
GenParser combines 3 monadic structures (parser monad, state monad,
error monad) into one data structure.
© M. Winter
9.19
COSC 4P41 – Functional Programming
Examples of monads (cont’d)
• State monad
– a state monad is a type of the form State a b = a -> (a,b)
where the type constructor is State a.
– An operation of this type can change the state (of type a) before
returning a value of type b.
– Example:
data Tree a = Nil | Node a (Tree a) (Tree a)
Moon
Ahmet
0
Dweezil
Ahmet
© M. Winter
Moon

1
2
1
0
9.20
COSC 4P41 – Functional Programming
Examples of monads (cont’d)
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)
© M. Winter
9.21
COSC 4P41 – Functional Programming
Examples of monads (cont’d)
numberTree :: Eq a => Tree a -> State
numberTree Nil = return Nil
numberTree (Node x t1 t2) = do num <nt1 <nt2 <return
a (Tree Int)
numberNode x
numberTree t1
numberTree t2
(Node num nt1 nt2)
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)
© M. Winter
9.22
COSC 4P41 – Functional Programming
Examples of monads (cont’d)
extract :: State a b -> b
extract (State st) = snd (st [])
numTree :: Eq a => Tree a => Tree Int
numTree = extract . numberTree
© M. Winter
9.23
COSC 4P41 – Functional Programming
Some Monad Functions
Module Prelude
•
•
•
•
•
readFile :: FilePath -> IO String
sequence :: Monad m => [m a] -> m [a]
sequence_ :: Monad m => [m a] -> m ()
mapM :: Monad m => (a -> m b) -> [a] -> m [b]
mapM_ :: Monad m => (a -> m b) -> [a] -> m ()
Module Data.IORef (updatable varibles, i.e., a state monad)
• newIORef :: a -> IO (IORef a)
• readIORef :: IORef a -> IO a
• writeIORef :: IORef a -> a -> IO ()
© M. Winter
9.24