Introduction to Programming
                    Assignment 5, 26 Oct, 2004
                      Due Mon 1 Nov, 2004

                             Deques

A deque, or double-ended queue, is a data structure that stores a
sequence of values.  Unlike a normal queue, new data can be added
to a deque at either end and, similarly, data can be extracted
from either end.

1. Implement the abstract datatype Deque in Haskell which
   supports the following functions:

   a. addfront :: (Deque a) -> a -> (Deque a)    
      -- Adds a value at the beginning of the deque

   b. addrear :: (Deque a) -> a -> (Deque a)    
      -- Adds a value at the end of the deque

   c. removefront :: (Deque a) -> (a,Deque a)
      -- Removes the value from the beginning of the deque,
      -- returns this value and the resulting deque

   d. removerear :: (Deque a) -> (a,Deque a)
      -- Removes the value from the end of the deque, returns
      -- this value and the resulting deque

   e. isemptyq :: (Deque a) -> Bool
      -- Tells whether the deque is empty

   f. emptydeque :: (Deque a)
      -- Returns an empty deque

   g. A value of type (Deque a) is displayed as a list with the
      end brackets being "<" and ">".  Thus, if the current
      values in the deque, from front to rear, are 21, 33 and 44,
      this deque would be displayed as "<21,33,44>".

   Your implementation should make visible only the datatype
   Deque and the functions that are specified in the question.

   Refer to "Stack.hs" below for an example of how to implement
   an abstract datatype in Haskell.

2. In a separate file "usedeque.hs", import the abstract datatype
   Deque and write a Haskell function

     builddeque :: [(String,a)] -> (Deque a)

   that takes as input a sequence of operations of the form
   ("addfront",v), ("addrear",v), ("removefront",v) and
   ("removerear",v) and returns the resulting deque.

   The operations ("addfront",v) and ("addrear",v) add v to the
   beginning and end of the deque, respectively.  The operations
   ("removefront",v) and ("removerear",v) remove the value from
   the beginning and end of the deque, respectively: in these two
   operations, the value v is irrelevant and is used only to
   provide a uniform type to the input list for "builddeque".

   For instance, 

     builddeque [("addrear",12),("addrear",8),("removefront",685),("addrear",37)]

   should return 

     <8,37>

   (Recall that 1(g) specifies this format for displaying deques).

   Refer to "usestack.hs" below for a sample of how to use an
   abstract datatype in another Haskell file.

======================================================================
Stack.hs
======================================================================

module Stack(Stack,pop,push,isempty,emptystack) where

data Stack a = Nil | Append a (Stack a)
     deriving (Eq,Ord)

instance Show a => Show (Stack a) where
  show Nil = ""
  show (Append x s) = (show x)++" "++(show s)
                                 
push :: (Stack a) -> a -> (Stack a)
push s a = Append a s

pop :: (Stack a) -> (a,(Stack a))
pop (Append a s) = (a,s)

isempty :: (Stack a) -> Bool
isempty Nil = True
isempty _   = False

emptystack :: (Stack a)
emptystack = Nil

======================================================================
usestack.hs
======================================================================

import Stack

--  construct:  takes a list of values and pushes the 
--              values into a stack from left to right

construct :: [a] -> (Stack a)
construct l = foldl push emptystack l

======================================================================