Enum Chunk

pub enum Chunk<A> {
    Empty,
    Single(A),
    Concat(Rc<Chunk<A>>, Rc<Chunk<A>>),
    Collect(Rc<RefCell<Vec<A>>>),
    TransformFlatten(Rc<Chunk<A>>, Rc<dyn Fn(A) -> Chunk<A>>),
}

A persistent data structure that provides efficient append and concatenation operations.

Overview

Chunk<A> is an immutable data structure that allows O(1) complexity for append and concatenation operations through structural sharing. It uses Rc (Reference Counting) for efficient memory management.

Performance

• Append operation: O(1)
• Concatenation operation: O(1)
• Converting to Vec: O(n)

Implementation Details

The data structure is implemented as an enum with three variants:

• Empty: Represents an empty chunk
• Append: Represents a single element appended to another chunk
• Concat: Represents the concatenation of two chunks

Examples

use tailcall_chunk::Chunk;

let mut chunk = Chunk::default();
chunk = chunk.append(1);
chunk = chunk.append(2);

let other_chunk = Chunk::default().append(3).append(4);
let combined = chunk.concat(other_chunk);

assert_eq!(combined.as_vec(), vec![1, 2, 3, 4]);

References

• Persistent Data Structures
• Structural Sharing

Variants

Empty

Represents an empty chunk with no elements

Single(A)

Represents a chunk containing exactly one element

Concat(Rc<Chunk<A>>, Rc<Chunk<A>>)

Represents the concatenation of two chunks, enabling O(1) concatenation

Collect(Rc<RefCell<Vec<A>>>)

Represents a collection of elements

TransformFlatten(Rc<Chunk<A>>, Rc<dyn Fn(A) -> Chunk<A>>)

Represents a lazy transformation that flattens elements

Implementations

impl<A> Chunk<A>

pub fn new(a: A) -> Self

Creates a new chunk containing a single element.

Arguments

• a - The element to store in the chunk

Examples

use tailcall_chunk::Chunk;

let chunk: Chunk<i32> = Chunk::new(100);
assert!(!chunk.is_null());

pub fn is_null(&self) -> bool

Returns true if the chunk is empty.

Examples

use tailcall_chunk::Chunk;

let chunk: Chunk<i32> = Chunk::default();
assert!(chunk.is_null());

let non_empty = chunk.append(42);
assert!(!non_empty.is_null());

pub fn append(self, a: A) -> Self

Append a new element to the chunk.

This operation has O(1) complexity as it creates a new Append variant that references the existing chunk through an Rc.

Examples

use tailcall_chunk::Chunk;

let chunk = Chunk::default().append(1).append(2);
assert_eq!(chunk.as_vec(), vec![1, 2]);

pub fn prepend(self, a: A) -> Self

Prepend a new element to the beginning of the chunk.

This operation has O(1) complexity as it creates a new Concat variant that references the existing chunk through an Rc.

Examples

use tailcall_chunk::Chunk;

let chunk = Chunk::default().prepend(1).prepend(2);
assert_eq!(chunk.as_vec(), vec![2, 1]);

pub fn concat(self, other: Chunk<A>) -> Chunk<A>

Concatenates this chunk with another chunk.

This operation has O(1) complexity as it creates a new Concat variant that references both chunks through Rcs.

Performance Optimization

If either chunk is empty, returns the other chunk instead of creating a new Concat variant.

Examples

use tailcall_chunk::Chunk;

let chunk1 = Chunk::default().append(1).append(2);
let chunk2 = Chunk::default().append(3).append(4);
let combined = chunk1.concat(chunk2);
assert_eq!(combined.as_vec(), vec![1, 2, 3, 4]);

pub fn transform(self, f: impl Fn(A) -> A + 'static) -> Self

Transforms each element in the chunk using the provided function.

This method creates a lazy representation of the transformation without actually performing it. The transformation is only executed when as_vec or as_vec_mut is called.

Performance

• Creating the transformation: O(1)
• Executing the transformation (during as_vec): O(n)

Arguments

• f - A function that takes a reference to an element of type A and returns a new element of type A

Examples

use tailcall_chunk::Chunk;

let chunk = Chunk::default().append(1).append(2).append(3);
// This operation is O(1) and doesn't actually transform the elements
let doubled = chunk.transform(|x| x * 2);
// The transformation happens here, when we call as_vec()
assert_eq!(doubled.as_vec(), vec![2, 4, 6]);

pub fn materialize(self) -> Chunk<A>

where A: Clone,

Materializes a chunk by converting it into a collected form.

This method evaluates any lazy transformations and creates a new chunk containing all elements in a Collect variant. This can be useful for performance when you plan to reuse the chunk multiple times, as it prevents re-evaluation of transformations.

Performance

• Time complexity: O(n) where n is the number of elements
• Space complexity: O(n) as it creates a new vector containing all elements

Examples

use tailcall_chunk::Chunk;

let chunk = Chunk::default()
    .append(1)
    .append(2)
    .transform(|x| x * 2);  // Lazy transformation

// Materialize the chunk to evaluate the transformation once
let materialized = chunk.materialize();

assert_eq!(materialized.as_vec(), vec![2, 4]);

pub fn transform_flatten(self, f: impl Fn(A) -> Chunk<A> + 'static) -> Self

Transforms each element in the chunk into a new chunk and flattens the result.

This method creates a lazy representation of the transformation without actually performing it. The transformation is only executed when as_vec or as_vec_mut is called.

Performance

• Creating the transformation: O(1)
• Executing the transformation (during as_vec): O(n)

Arguments

• f - A function that takes an element of type A and returns a new Chunk<A>

Examples

use tailcall_chunk::Chunk;

let chunk = Chunk::default().append(1).append(2);
// Transform each number x into a chunk containing [x, x+1]
let expanded = chunk.transform_flatten(|x| {
    Chunk::default().append(x).append(x + 1)
});
assert_eq!(expanded.as_vec(), vec![1, 2, 2, 3]);

pub fn as_vec(&self) -> Vec<A>

where A: Clone,

Converts the chunk into a vector of references to its elements.

This operation has O(n) complexity where n is the number of elements in the chunk.

Examples

use tailcall_chunk::Chunk;

let chunk = Chunk::default().append(1).append(2).append(3);
assert_eq!(chunk.as_vec(), vec![1, 2, 3]);

pub fn as_vec_mut(&self, buf: &mut Vec<A>)

where A: Clone,

Helper method that populates a vector with references to the chunk’s elements.

This method is used internally by as_vec to avoid allocating multiple vectors during the traversal.

Arguments

• buf - A mutable reference to a vector that will be populated with references to the chunk’s elements

Trait Implementations

impl<A: Clone> Clone for Chunk<A>

fn clone(&self) -> Chunk<A>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<A> Default for Chunk<A>

fn default() -> Self

Creates a new empty chunk.

This is equivalent to using Chunk::Empty.

impl<A> FromIterator<A> for Chunk<A>

fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self

Creates a chunk from an iterator.

Examples

use tailcall_chunk::Chunk;

let vec = vec![1, 2, 3];
let chunk: Chunk<_> = vec.into_iter().collect();
assert_eq!(chunk.as_vec(), vec![1, 2, 3]);