Introduction to Programming

Assignment 5

Date: Tue, 26 October 2004

Due on: Mon, 1 November 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:

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

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

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

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

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

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

   7. 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 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 for a sample of how to use an abstract datatype in another Haskell file.