Purely functional data structures are data structures that are designed to have good performance when implemented using pure functional programming techniques. This typically means that no mutable state is used in the implementation. As Tcl's strings are immutable and everything is a string, many Tcl data structures are also purely functional in this sense, such as lists and dicts. Therefore, many of the same techniques can often be adapted when creating data structures in Tcl.
(Tcl also has mutable variables and arrays so can support traditional stateful data structures as well, but we will ignore those here).
The seminal work in this field is Chris Okasaki's thesis [L1 ] and subsequent book [L2 ]. This discusses many of the core techniques, such as lazy evaluation or memoizing, along with example data structures.
The examples do not always translate directly into Tcl, as most functional programming languages favour pointer-based data structures such as linked lists and balanced trees. Tcl is almost unique amongst functional programming languages as its reference-counting based memory management allows efficient use of arrays and hash-tables that are prohibitively expensive in most functional languages.
An example of such a technique is given on Implementing FIFO queues. By implementing the queue as a pair of lists - one in normal order, and one reversed - we can get good performance for both put/push and get/pop operations. This is known as an amortized queue in the literature.