05 07 13

Page 1

Principles of Programming Languages 2013.07.05 Notes • Total available time: 1h 30’. • You may use any written material you need. • You cannot use computers, phones or laptops during the exam. 1 Haskell (13 points) Consider the state monad as seen in class, i.e. defined by: newtype State st a = State (st -> (st, a)) instance Monad (State state) where return x = let f t = (t,x) in State f State f >>= g = State (\oldstate -> let (newstate, val) = f oldstate State f’ = g val in f’ newstate) getState :: State state state getState = State (\state -> (state, state)) putState :: state -> State state () putState new = State (\_ -> (new, ())) 1. Define the monadic function mapListM :: (t -> State st a) -> [t] -> State st [a] that applies its first argument (another monadic function, as you can see by the signature) to every element of the list passed as its second argument (i.e. like a map). 2. Define the monadic function numberList :: Num st => [st] -> State st [(st, st)] , based on mapListM, that takes as input a list of numbers and returns a list of pairs of numbers ( x, y), where the first component is the same as the value x at the same position in the input list, while y is the state when x was reached. The state is incremented by x, when x is reached. For example: let State f = (numberList [1,3,22,-5]) in f 0 -- the initial value of the state is 0 should evaluate to (21, [(1,1),(3,4),(22,26),(-5,21)]) , i.e. the last value of the state is 21. 1 2 Scheme/Ruby (9 points) Implement an analogous of the numberList function of the previous exercise either in Scheme or in Ruby (it is not necessary to use the same monadic construction). For instance, the procedure call (numberlist ’(1 3 22 -5) 0) , where the second parameter is the initial state, should return ’((1 . 1) (3 . 4) (22 .…