1structure Stack :> Stack =
2struct
3
4   exception EmptyStack
5
6   datatype 'item stack =
7       Empty |
8       Node of 'item * 'item stack
9
10   fun isEmpty( Node( _ , S)) = false
11    |  isEmpty _          = true
12
13   fun empty() = Empty
14
15   fun push( x, S ) = Node( x, S )
16
17   fun pop( Empty ) = raise EmptyStack
18   |   pop( Node( x, S) ) = S
19
20   fun top( Empty ) = raise EmptyStack
21   |   top( Node( x, S ) ) = x
22
23   fun stack2set (Empty, st) = st
24   |   stack2set (Node(x,S),st) = stack2set(S, Binaryset.add(st,x))
25
26end
27