Functional data structures and monads

Functional data structures are data structures that follow the principle of immutability and inductive (or recursive) definition. Immutability means that any modification of the data structure would result in a new data structure, and any old reference to the original version would still have access to the original version. Inductive definition means that the definition of the structure is defined as a composition of smaller versions of the same data structure. Take, for example, our linked list. When we add an element to or remove an element from the beginning of the list, it will modify the linked list. That means any reference to the linked list will now hold a reference to the modified linked list. This doesn't conform to the principle of immutability. A functional linked list would make sure that the older references still held reference to an unmodified version. We will discuss how to do it in the next section.