Since Push requires stacks to manipulate its data, we need an implementation of this data structure. There is of course a .NET implementation, however, it is not a “functional” data structure, in a sense that it is mutable. It is easy enough to implement our own, purely functional, immutable stack.

F# list is a logical choice for an underlying implementation. It derives from Seq (i.e. implements all IEnumerable flavors), has a useful length property which we would like to have for our stack as well:

What remains is to implement basic operations, which are all static members of the Stack module.

These are pretty straightforward. pop function has a slight quirk: we would like to return both the value of the head of the stack as well as “the rest” of the stack. So the return type in this case is a tuple.

Another slight irregularity: stack functions work on…