tailcall_chunk/lib.rs
1//! A Rust implementation of a persistent data structure that provides O(1) append and concatenation operations
2//! through structural sharing.
3//!
4//! # Overview
5//! `Chunk` is a persistent data structure that offers:
6//! - **O(1) Append Operations**: Add elements to your chunk in constant time
7//! - **O(1) Concatenation**: Combine two chunks efficiently
8//! - **Immutable/Persistent**: All operations create new versions while preserving the original
9//! - **Memory Efficient**: Uses structural sharing via reference counting
10//! - **Safe Rust**: Implemented using 100% safe Rust
11//!
12//! # Theoretical Background
13//!
14//! This implementation is inspired by the concepts presented in Hinze and Paterson's work on
15//! [Finger Trees](https://en.wikipedia.org/wiki/Finger_tree), though simplified for our specific use case.
16//! While our implementation differs in structure, it shares similar performance goals and theoretical foundations.
17//!
18//! ## Relationship to Finger Trees
19//!
20//! Finger Trees are a functional data structure that supports:
21//! - Access to both ends in amortized constant time
22//! - Concatenation in logarithmic time
23//! - Persistence through structural sharing
24//!
25//! Our `Chunk` implementation achieves similar goals through a simplified approach:
26//! - We use `Append` nodes for constant-time additions
27//! - The `Concat` variant enables efficient concatenation
28//! - `Rc` (Reference Counting) provides persistence and structural sharing
29//!
30//! # Example Usage
31//! ```rust
32//! use tailcall_chunk::Chunk;
33//!
34//! // Create a new chunk and append some elements
35//! let chunk1 = Chunk::default()
36//! .append(1)
37//! .append(2);
38//!
39//! // Create another chunk
40//! let chunk2 = Chunk::default()
41//! .append(3)
42//! .append(4);
43//!
44//! // Concatenate chunks in O(1) time
45//! let combined = chunk1.concat(chunk2);
46//!
47//! // Convert to vector when needed
48//! assert_eq!(combined.as_vec(), vec![1, 2, 3, 4]);
49//! ```
50//!
51//! # Performance Characteristics
52//!
53//! ## Time Complexity Analysis
54//!
55//! | Operation | Worst Case | Amortized | Space |
56//! | --------------------- | ---------- | ------------ | ------------ |
57//! | `new()` | O(1) | O(1) | O(1) |
58//! | `append()` | O(1) | O(1) | O(1) |
59//! | `concat()` | O(1) | O(1) | O(1) |
60//! | `transform()` | O(1) | O(1) | O(1) |
61//! | `transform_flatten()` | O(1) | O(1) | O(1) |
62//! | `as_vec()` | O(n) | O(n) | O(n) |
63//! | `clone()` | O(1) | O(1) | O(1) |
64//!
65//! ## Amortized Analysis Details
66//!
67//! ### Append Operation
68//! The `append` operation is O(1) amortized because:
69//! - The actual append is always O(1) as it only creates a new `Append` node
70//! - No rebalancing is required
71//! - Memory allocation is constant time
72//!
73//! ### Concat Operation
74//! The `concat` operation achieves O(1) amortized time through:
75//! - Lazy evaluation: immediate concatenation is O(1)
76//! - The actual work is deferred until `as_vec()` is called
77//! - No immediate copying or restructuring of data
78//!
79//! ### Transform Operations
80//! Both `transform` and `transform_flatten` are O(1) amortized because:
81//! - They create a new node with a transformation function
82//! - Actual transformation is deferred until materialization
83//! - No immediate computation is performed on elements
84//!
85//! ### as_vec Operation
86//! The `as_vec` operation is O(n) because:
87//! - It must process all elements to create the final vector
88//! - For a chunk with n elements:
89//! - Basic traversal: O(n)
90//! - Applying deferred transformations: O(n)
91//! - Memory allocation and copying: O(n)
92//!
93//! ### Memory Usage Patterns
94//!
95//! The space complexity has interesting properties:
96//! - Immediate space usage for operations is O(1)
97//! - Deferred space cost accumulates with operations
98//! - Final materialization requires O(n) space
99//! - Structural sharing reduces memory overhead for clones and versions
100//!
101//! ```rust
102//! use tailcall_chunk::Chunk;
103//!
104//! // Each operation has O(1) immediate cost
105//! let chunk = Chunk::default()
106//! .append(1) // O(1) time and space
107//! .append(2) // O(1) time and space
108//! .transform(|x| x + 1); // O(1) time and space
109//!
110//! // O(n) cost is paid here
111//! let vec = chunk.as_vec();
112//! ```
113//!
114//! # Implementation Details
115//!
116//! The `Chunk<A>` type is implemented as an enum with four variants:
117//! - `Empty`: Represents an empty chunk
118//! - `Append`: Represents a single element appended to another chunk
119//! - `Concat`: Represents the concatenation of two chunks
120//! - `TransformFlatten`: Represents a lazy transformation and flattening of elements
121//!
122//! The data structure achieves its performance characteristics through:
123//! - Structural sharing using `Rc`
124//! - Lazy evaluation of concatenation and transformations
125//! - Immutable operations that preserve previous versions
126//!
127//! # Memory Efficiency
128//!
129//! The `Chunk` type uses structural sharing through reference counting (`Rc`), which means:
130//! - Appending or concatenating chunks doesn't copy the existing elements
131//! - Memory is automatically freed when no references remain
132//! - Multiple versions of the data structure can coexist efficiently
133//!
134//! ```rust
135//! use tailcall_chunk::Chunk;
136//!
137//! let original = Chunk::default().append(1).append(2);
138//! let version1 = original.clone().append(3); // Efficient cloning
139//! let version2 = original.clone().append(4); // Both versions share data
140//! ```
141//!
142//! # References
143//!
144//! 1. Ralf Hinze and Ross Paterson. "Finger Trees: A Simple General-purpose Data Structure",
145//! Journal of Functional Programming 16(2):197-217, 2006.
146//! 2. Chris Okasaki. "Purely Functional Data Structures", Cambridge University Press, 1998.
147
148mod chunk;
149pub use chunk::*;