Exercises for Monads

1. IO

The following defines a simple language (strings in ``...'' are terminals):

<Request> ::= <Request0> | <Request1>`` ''String
<Request0> ::= ``Close'' | ``Stop''
<Request1> ::= ``Open'' | ``Append''
Write an interactive program that accepts <Request>s one per input line and processes them while keeping as internal state a stack of output channel descriptions of type Maybe String, where the topmost element of that stack should be considered as active. In the start state, Nothing is the only stack element and therefore active; Nothing should be interpreted as stdout, and Just p as file name p.

``Open filename'' should push the file with name ``filename'' as new active output description.

``Append any_string'' should append the line ``any_string'' to the current output channel.

``Close'' should close the current output channel i.e., remove it from the stack.

``Stop'' terminates interaction.

Produce a control message after every action and pay attention to complete error handling.

2. State Monads

The following data type definition is given. 
> data STFun s x = STFun (s -> (s,x))
  1. Define instances of Functor and Monad for STFun s and prove the respective laws.
  2. Define the following Haskell functions that enable the use of a functional data type interface in an ``imperative'' way: 
    > clift  :: (s                -> s)                -> STFun s ()
> clift1 :: (s -> a           -> s) -> a           -> STFun s ()
> clift2 :: (s -> a -> b      -> s) -> a -> b      -> STFun s ()
> clift3 :: (s -> a -> b -> c -> s) -> a -> b -> c -> STFun s ()

> rlift  :: (s                -> r)                -> STFun s r
> rlift1 :: (s -> a           -> r) -> a           -> STFun s r
> rlift2 :: (s -> a -> b      -> r) -> a -> b      -> STFun s r
> rlift3 :: (s -> a -> b -> c -> r) -> a -> b -> c -> STFun s r
  3. Implement a Haskell module STFM defining an abstract data type STFM a b r wrapping

    STFun (FiniteMap a b) r

    and exporting also access functions for sequential access to the FiniteMap hidden inside STFM, without ever providing direct external access to that FiniteMap. Transfer also the instance of Functor and Monad from STFun to STFM.

3. Interpreter

The following type declarations define a simple imperative programming language --- programs are of type [Com], where every command either assigns the value of an expression to a variable (Assign), or assigns the next value from the input stream to a variable (Read), or appends the value of an expression to the output stream (Write), or is a While loop. The While loop should be terminated if its first argument assumes the value ``0''. Expressions are standard arithmetic expressions that can also refer to the values of variables (Ref). 

> data Com = Assign Var Exp
>          | Read Var
>          | Write Exp
>          | While Exp [Com]

> type Var = String

> data Exp = Ref Var
>          | Num Integer
>          | Bin BinOp Exp Exp

> data BinOp = Plus
>            | Minus
>            | Times
>            | Div
  1. Use this programming language to write a program for calculating the factorial function.

  2. Write an interpreter for this programming language: 

    > interpret :: [Com] -> [Integer] -> [Integer]
    This interpreter takes a program and a list of input values available to Read as arguments and maps them to the list of the output values produced by Write.

    For managing the variable environment, use the monad STFM from problem 2!

    If you really cannot get started, you find a skeleton in Interp.xhs.

  3. Implement a command-line interface interpreter :: IO () similar to hugs for interpret.

  4. Declare instances of Read and Show for 

    type Prog = [Com]
    geared towards a ``normal'' text representation of programs.

    Hint: Define appropriate instances of Show and Read for the types BinOp, Exp and Com.

    Pay attention to instantiate showList and readList for Com in a useful way.

    5. Extend your I/O interface so that you can at least

    1. load programs from files,
    2. start loaded programs,
    3. interrupt running programs (at least while they are waiting for input to Read),
    4. display the loaded program.

CAS 781: Functional Programming 2003