5.3.3 Bag

In order to accumulate results (recognized single categories), we define a second abstract datatype representing a bag of results. For simplicity, we implement bags by stacks, even though this is not very efficient. A better implementation that relys directely on cells is given in Section on Bags in the Chapter on Stateful Data Structures:

<declare NewBag>=

%% implement bags through stacks
declare NewBag = NewStack

We will now exploit that stacks do also have a function that converts their actural contents into a list, i.e. we exploit bags with the following type (that is compatible with that of a stack).

 unit(
    push  : Value -> 
    toList: -> list(Value)
    ... 
   ) 

If B is a bag, a new item X can be added to it with {B.push X}, and the list of its contents can be obtained with {B.toList}.