Functional Data Structures
A functional data structure is one that does not make use of any imperative features. That is, no operations of the data structure have any side effects. It's possible to build functional data structures both in functional languages and in imperative languages.
Functional data structures have the property of being persistent: updating the data structure with one of its operations does not change the existing version of the data structure but instead produces a new version. Both exist and both can still be accessed. A good language implementation will ensure that any parts of the data structure that are not changed by an operation will be shared between the old version and the new version. Any parts that do change will be copied so that the old version may persist. The opposite of a persistent data structure is an ephemeral data structure: changes are destructive, so that only one version exists at any time. Both persistent and ephemeral data structures can be built in both functional and imperative languages.
ListStack module above is functional: the
do not mutate the underlying list, but instead return a new list. We can
see that in the following utop session (in which we assume the
has been defined as
module ListStack = struct ..., without the module type annotation
: Stack we added above):
# open ListStack;; # let s = push 1 (push 2 empty);; val s : int list = [1; 2] # let s' = pop s;; val s' : int list =  # s;; - : int list = [1; 2]
s is unchanged by the
pop operation; both versions of the stack coexist.
Stack module type gives us a strong hint that the data structure is functional
in the types is provides for
val push : 'a -> 'a stack -> 'a stack val pop : 'a stack -> 'a stack
Both of those take a stack as an argument and return a new stack as a result.
An ephemeral data structure usually would not bother to return a stack.
In Java, for example, similar methods might return
void; the equivalent
in OCaml would be returning