1. Create the following ADTs.

(a) Write the constructor function makestk, predicate function emptystk and mutator functions pushstk and popstk:

i. makestk returns a new stack in the form of a tagged tuple: ('stack',[]).

e.g. >>> cellstk=makestk()

>>> cellstk

('stack', [])

ii. emptystk returns True or False depending on whether the given stack is empty or not.

e.g. >>> emptystk(cellstk)

True

iii. pushstk accepts a stack and an element, and adds the element to the stack at position 0 (see part (b) below for the creation of cell0).

e.g. >>> pushstk(cellstk,cell0)

>>> cellstk

('stack', [('cell', (0, 0), ['t', 'b', 'r', 'l'])])

iv. popstk removes the element at position 0 of the given stack.

e.g. >>> popstk(cellstk)

('cell', (0, 0), ['t', 'b', 'r', 'l'])

>>> cellstk

('stack', [])

(b) Write a constructor function called makecell, accessor functions getx, gety and getwalls, and mutator functions removetw, removebw, removerw, removelw.

i. makecell accepts a tuple which consists of the x and y co-ordinate of the cell being created. It returns a cell in the form of a tagged tuple:

('cell',(x,y),['t','b','r','l']).

The list represents the four walls of the cell: top, bottom, right and left.

e.g. >>> cell0=makecell((0,0))

>>> cell0

('cell', (0, 0), ['t', 'b', 'r', 'l'])

ii. getx and gety return the x and y co-ordinates (respectively) of a given cell.

e.g. >>> getx(cell0)

0

iii. getwalls returns the list of walls that are intact for a given cell

e.g. >>> getwalls(cell0)

['t', 'b', 'r', 'l']

iv. remove?w removes the associated wall from the list of walls of a given cell.

e.g. >>> removetw(cell0)

>>> cell0

('cell', (0, 0), ['b', 'r', 'l'])