sutton036

Purely functional data structures have the following advantages: Persistence: old versions can be reused safe in the knowledge that they cannot have been changed. Sharing: many versions of a data structure can be kept simultaneously with relatively modest memory requirements. Thread safety: any mutation is hidden inside lazy thunks (if any) and, therefore, thread safety is handled by the language implementation. Simplicity: not having to keep track of state changes often makes purely functional data structures simpler to use, particularly in the context of concurrency. Incrementality: purely functional data structures are composed of many tiny parts, making them ideal for incremental garbage collection, leading to lower latencies. Purely functional data structures also have the potential to be beneficial in the context of parallel programming for multicores. However, efficient multicore parallelism requires predictable locality in order to leverage caches and avoid getting bottlen...

One of the concerns expressed by some of the remaining OCaml users, such as Yaron Minsky of Jane St Capital, is the relative performance of F# in the context of purely functional data structures. Specifically, language implementations like OCaml are heavily optimized for this use case due to their legacy and on-going use for applications such as theorem proving, which benefit greatly from the efficient handling of purely functional data structures. Historically, most users of imperative languages such as Java and C# have not required this kind of performance and, consequently, their implementations have not been optimized for this style of programming. However, the recently released .NET 4 includes a new garbage collector and we have found that it provides substantial performance improvements in the context of purely functional data structures which is of particular benefit to F# developers. We recently examined the performance of four different purely functional heap implementati...

Here's Markus Mottl's OCaml translation of Okasaki's purely functional leftist heap: module LeftistHeap (Element : ORDERED) : (HEAP with module Elem = Element) = struct module Elem = Element type heap = E | T of int * Elem.t...