MutableList-Guide.md

MutableList: A Real-World Guide

Table of Contents

1. Introduction & Core Concepts
2. Basic Usage Patterns
3. Real-World Examples
4. Advanced Features Deep Dive
5. Practical Patterns & Best Practices
6. Integration Examples

Introduction & Core Concepts

The Problem MutableList Solves

When building applications that require frequent insertion and deletion at arbitrary positions, JavaScript arrays become a performance bottleneck. Traditional array operations like inserting or removing elements from the middle require shifting all subsequent elements, leading to O(n) complexity:

// Traditional approach - inefficient insertion/deletion with arrays
class TaskManager {
  private tasks: Task[] = []
  
  // O(n) - must shift all elements after insertion point
  insertTaskAt(index: number, task: Task): void {
    this.tasks.splice(index, 0, task)
  }
  
  // O(n) - must shift all elements after deletion point
  removeTaskAt(index: number): Task | undefined {
    return this.tasks.splice(index, 1)[0]
  }
  
  // O(n) - linear search to find and remove
  removeTask(taskId: string): boolean {
    const index = this.tasks.findIndex(t => t.id === taskId)
    if (index >= 0) {
      this.tasks.splice(index, 1)
      return true
    }
    return false
  }
  
  // Moving tasks around requires multiple O(n) operations
  moveTask(fromIndex: number, toIndex: number): void {
    const [task] = this.tasks.splice(fromIndex, 1) // O(n)
    this.tasks.splice(toIndex, 0, task) // O(n)
  }
}

// Implementing undo/redo becomes complex and memory-intensive
class UndoableEditor {
  private content: string[] = []
  private history: string[][] = []
  
  // O(n) memory copy for each state save
  saveState(): void {
    this.history.push([...this.content]) // Full array copy
  }
  
  // O(n) insertion with expensive state management
  insertLineAt(index: number, line: string): void {
    this.saveState()
    this.content.splice(index, 0, line)
  }
  
  // Memory grows quickly with large documents
  undo(): void {
    const previousState = this.history.pop()
    if (previousState) {
      this.content = previousState // Another O(n) copy
    }
  }
}

This approach leads to:

• Performance degradation - O(n) complexity for insertions, deletions, and moves
• Memory inefficiency - Array operations require copying and shifting elements
• Complex state management - Maintaining history or undo operations is expensive
• Poor scalability - Performance degrades linearly with data size

The MutableList Solution

Effect's MutableList provides a doubly-linked list implementation that offers O(1) insertion and deletion at any position when you have a reference to the node, making it ideal for scenarios requiring frequent modifications:

import { MutableList } from "effect"

// Efficient task management with MutableList
class EfficientTaskManager {
  private tasks = MutableList.empty<Task>()
  private taskNodes = new Map<string, Task>()
  
  // O(1) - append to end
  addTask(task: Task): void {
    MutableList.append(this.tasks, task)
    this.taskNodes.set(task.id, task)
  }
  
  // O(1) - prepend to beginning
  addUrgentTask(task: Task): void {
    MutableList.prepend(this.tasks, task)
    this.taskNodes.set(task.id, task)
  }
  
  // O(1) - remove from either end
  removeFirstTask(): Task | undefined {
    return MutableList.shift(this.tasks)
  }
  
  removeLastTask(): Task | undefined {
    return MutableList.pop(this.tasks)
  }
  
  // Efficient iteration without array copies
  forEachTask(callback: (task: Task) => void): void {
    MutableList.forEach(this.tasks, callback)
  }
  
  // O(1) reset for bulk operations
  clearAllTasks(): void {
    MutableList.reset(this.tasks)
    this.taskNodes.clear()
  }
}

// Memory-efficient undo system
class EfficientEditor {
  private lines = MutableList.empty<string>()
  private snapshots: MutableList<string>[] = []
  
  // O(1) line operations
  addLine(content: string): void {
    MutableList.append(this.lines, content)
  }
  
  insertLineAtBeginning(content: string): void {
    MutableList.prepend(this.lines, content)
  }
  
  // Efficient state snapshots - only store references
  saveSnapshot(): void {
    // Create new list from current state
    const snapshot = MutableList.fromIterable(this.lines)
    this.snapshots.push(snapshot)
  }
  
  // Quick restoration without expensive copies
  restoreSnapshot(): void {
    const snapshot = this.snapshots.pop()
    if (snapshot) {
      MutableList.reset(this.lines)
      MutableList.forEach(snapshot, line => MutableList.append(this.lines, line))
    }
  }
}

Key Concepts

Doubly-Linked Structure: Each element maintains references to both previous and next nodes, enabling efficient bidirectional traversal and modification.

O(1) Head/Tail Operations: Adding or removing elements from either end of the list is constant time.

Mutable by Design: Unlike immutable lists, MutableList is designed for scenarios where mutation is necessary for performance.

Iterator Support: Implements JavaScript's Iterable interface for seamless integration with for-of loops and array utilities.

Basic Usage Patterns

Pattern 1: Creating and Populating Lists

import { MutableList } from "effect"

// Creating empty lists
const numbers = MutableList.empty<number>()
const names = MutableList.empty<string>()

// Creating from existing data
const fruits = MutableList.fromIterable(["apple", "banana", "cherry"])
const priorities = MutableList.make(1, 2, 3, 4, 5)

// Building lists incrementally
const shoppingList = MutableList.empty<string>()
MutableList.append(shoppingList, "milk")
MutableList.append(shoppingList, "bread")
MutableList.prepend(shoppingList, "urgent: medicine") // Goes to front

Pattern 2: Head and Tail Operations

// Queue-like behavior (FIFO)
const taskQueue = MutableList.empty<Task>()

// Add to back of queue
MutableList.append(taskQueue, { id: "1", priority: "normal" })
MutableList.append(taskQueue, { id: "2", priority: "normal" })

// Process from front of queue
while (!MutableList.isEmpty(taskQueue)) {
  const nextTask = MutableList.shift(taskQueue) // Remove from front
  if (nextTask) {
    processTask(nextTask)
  }
}

// Stack-like behavior (LIFO)
const undoStack = MutableList.empty<Action>()

// Push operations
MutableList.append(undoStack, { type: "insert", data: "hello" })
MutableList.append(undoStack, { type: "delete", data: "world" })

// Pop operations
const lastAction = MutableList.pop(undoStack) // Remove from back
if (lastAction) {
  undoAction(lastAction)
}

Pattern 3: Iteration and Inspection

const inventory = MutableList.make("widgets", "gadgets", "tools")

// Safe head/tail access
const firstItem = MutableList.head(inventory) // "widgets" | undefined
const lastItem = MutableList.tail(inventory)  // "tools" | undefined

// Length and emptiness checks
const itemCount = MutableList.length(inventory) // 3
const isEmpty = MutableList.isEmpty(inventory)  // false

// Efficient iteration
MutableList.forEach(inventory, (item) => {
  console.log(`Inventory item: ${item}`)
})

// JavaScript iteration protocols
for (const item of inventory) {
  console.log(`Processing: ${item}`)
}

// Convert to array when needed (creates new array)
const inventoryArray = Array.from(inventory)

Real-World Examples

Example 1: Real-Time Chat Message Buffer

Building a chat application that maintains a scrollable message history with efficient insertion and cleanup:

import { MutableList, Effect } from "effect"

interface ChatMessage {
  id: string
  userId: string
  content: string
  timestamp: Date
  edited?: boolean
}

class ChatMessageBuffer {
  private messages = MutableList.empty<ChatMessage>()
  private readonly maxMessages: number
  
  constructor(maxMessages: number = 1000) {
    this.maxMessages = maxMessages
  }
  
  // O(1) - Add new message to end
  addMessage(message: ChatMessage): Effect.Effect<void> {
    return Effect.gen(function* () {
      MutableList.append(this.messages, message)
      
      // Maintain buffer size - O(1) removal from front
      if (MutableList.length(this.messages) > this.maxMessages) {
        MutableList.shift(this.messages)
      }
    }.bind(this))
  }
  
  // O(1) - Add system message to front (urgent notifications)
  addSystemMessage(message: ChatMessage): Effect.Effect<void> {
    return Effect.gen(function* () {
      MutableList.prepend(this.messages, message)
      
      // Remove oldest message if needed
      if (MutableList.length(this.messages) > this.maxMessages) {
        MutableList.pop(this.messages)
      }
    }.bind(this))
  }
  
  // Efficient message processing without array copies
  processRecentMessages(processor: (msg: ChatMessage) => Effect.Effect<void>): Effect.Effect<void> {
    return Effect.gen(function* () {
      let processed = 0
      const maxRecent = 50
      
      for (const message of this.messages) {
        if (processed >= maxRecent) break
        yield* processor(message)
        processed++
      }
    }.bind(this))
  }
  
  // Get messages for UI rendering
  getRecentMessages(count: number): ChatMessage[] {
    const result: ChatMessage[] = []
    let collected = 0
    
    for (const message of this.messages) {
      if (collected >= count) break
      result.push(message)
      collected++
    }
    
    return result
  }
  
  // Efficient cleanup for memory management
  clearOldMessages(): Effect.Effect<number> {
    return Effect.gen(function* () {
      const cutoffTime = new Date(Date.now() - 24 * 60 * 60 * 1000) // 24 hours ago
      let removedCount = 0
      
      // Remove old messages from the front
      while (!MutableList.isEmpty(this.messages)) {
        const oldest = MutableList.head(this.messages)
        if (oldest && oldest.timestamp < cutoffTime) {
          MutableList.shift(this.messages)
          removedCount++
        } else {
          break
        }
      }
      
      return removedCount
    }.bind(this))
  }
}

// Usage in chat application
const createChatService = Effect.gen(function* () {
  const messageBuffer = new ChatMessageBuffer(500)
  
  const addUserMessage = (userId: string, content: string) =>
    messageBuffer.addMessage({
      id: crypto.randomUUID(),
      userId,
      content,
      timestamp: new Date()
    })
  
  const addSystemAlert = (content: string) =>
    messageBuffer.addSystemMessage({
      id: crypto.randomUUID(),
      userId: "system",
      content,
      timestamp: new Date()
    })
  
  return { messageBuffer, addUserMessage, addSystemAlert }
})

Example 2: Task Scheduler with Priority Insertion

Implementing a task scheduler that efficiently manages task queues with priority-based insertion:

import { MutableList, Effect, Option } from "effect"

interface ScheduledTask {
  id: string
  priority: "low" | "normal" | "high" | "urgent"
  execute: () => Effect.Effect<void>
  createdAt: Date
  retryCount: number
}

class PriorityTaskScheduler {
  private urgentTasks = MutableList.empty<ScheduledTask>()
  private highTasks = MutableList.empty<ScheduledTask>()
  private normalTasks = MutableList.empty<ScheduledTask>()
  private lowTasks = MutableList.empty<ScheduledTask>()
  private isProcessing = false
  
  // O(1) task insertion based on priority
  scheduleTask(task: ScheduledTask): Effect.Effect<void> {
    return Effect.gen(function* () {
      switch (task.priority) {
        case "urgent":
          MutableList.append(this.urgentTasks, task)
          break
        case "high":
          MutableList.append(this.highTasks, task)
          break
        case "normal":
          MutableList.append(this.normalTasks, task)
          break
        case "low":
          MutableList.append(this.lowTasks, task)
          break
      }
      
      // Start processing if not already running
      if (!this.isProcessing) {
        yield* this.startProcessing()
      }
    }.bind(this))
  }
  
  // Add urgent task to front of urgent queue
  scheduleUrgentTask(task: ScheduledTask): Effect.Effect<void> {
    return Effect.gen(function* () {
      const urgentTask = { ...task, priority: "urgent" as const }
      MutableList.prepend(this.urgentTasks, urgentTask)
      
      if (!this.isProcessing) {
        yield* this.startProcessing()
      }
    }.bind(this))
  }
  
  // O(1) task retrieval following priority order
  private getNextTask(): Option.Option<ScheduledTask> {
    // Check urgent tasks first
    if (!MutableList.isEmpty(this.urgentTasks)) {
      const task = MutableList.shift(this.urgentTasks)
      return task ? Option.some(task) : Option.none()
    }
    
    // Then high priority
    if (!MutableList.isEmpty(this.highTasks)) {
      const task = MutableList.shift(this.highTasks)
      return task ? Option.some(task) : Option.none()
    }
    
    // Then normal priority
    if (!MutableList.isEmpty(this.normalTasks)) {
      const task = MutableList.shift(this.normalTasks)
      return task ? Option.some(task) : Option.none()
    }
    
    // Finally low priority
    if (!MutableList.isEmpty(this.lowTasks)) {
      const task = MutableList.shift(this.lowTasks)
      return task ? Option.some(task) : Option.none()
    }
    
    return Option.none()
  }
  
  private startProcessing(): Effect.Effect<void> {
    return Effect.gen(function* () {
      this.isProcessing = true
      
      while (true) {
        const nextTaskOption = this.getNextTask()
        
        if (Option.isNone(nextTaskOption)) {
          break // No more tasks
        }
        
        const task = nextTaskOption.value
        
        // Execute task with retry logic
        const result = yield* Effect.gen(function* () {
          return yield* task.execute()
        }).pipe(
          Effect.catchAll((error) => this.handleTaskFailure(task, error))
        )
      }
      
      this.isProcessing = false
    }.bind(this))
  }
  
  private handleTaskFailure(task: ScheduledTask, error: unknown): Effect.Effect<void> {
    return Effect.gen(function* () {
      if (task.retryCount < 3) {
        // Retry with backoff - add to appropriate queue
        const retryTask = {
          ...task,
          retryCount: task.retryCount + 1
        }
        
        yield* Effect.sleep(`${Math.pow(2, task.retryCount)} seconds`)
        
        // Demote priority for retries
        const newPriority = task.priority === "urgent" ? "high" :
                          task.priority === "high" ? "normal" :
                          task.priority === "normal" ? "low" : "low"
        
        yield* this.scheduleTask({ ...retryTask, priority: newPriority })
      } else {
        // Log failure and move on
        console.error(`Task ${task.id} failed after ${task.retryCount} retries:`, error)
      }
    }.bind(this))
  }
  
  // Get current queue status
  getQueueStatus(): Effect.Effect<{
    urgent: number
    high: number
    normal: number
    low: number
    total: number
  }> {
    return Effect.succeed({
      urgent: MutableList.length(this.urgentTasks),
      high: MutableList.length(this.highTasks),
      normal: MutableList.length(this.normalTasks),
      low: MutableList.length(this.lowTasks),
      total: MutableList.length(this.urgentTasks) + 
             MutableList.length(this.highTasks) + 
             MutableList.length(this.normalTasks) + 
             MutableList.length(this.lowTasks)
    })
  }
  
  // Clear all tasks of a specific priority
  clearPriorityQueue(priority: ScheduledTask["priority"]): Effect.Effect<number> {
    return Effect.gen(function* () {
      let clearedCount = 0
      
      switch (priority) {
        case "urgent":
          clearedCount = MutableList.length(this.urgentTasks)
          MutableList.reset(this.urgentTasks)
          break
        case "high":
          clearedCount = MutableList.length(this.highTasks)
          MutableList.reset(this.highTasks)
          break
        case "normal":
          clearedCount = MutableList.length(this.normalTasks)
          MutableList.reset(this.normalTasks)
          break
        case "low":
          clearedCount = MutableList.length(this.lowTasks)
          MutableList.reset(this.lowTasks)
          break
      }
      
      return clearedCount
    }.bind(this))
  }
}

// Usage example
const taskSchedulerExample = Effect.gen(function* () {
  const scheduler = new PriorityTaskScheduler()
  
  // Schedule various tasks
  yield* scheduler.scheduleTask({
    id: "daily-backup",
    priority: "low",
    execute: () => Effect.succeed(console.log("Running daily backup")),
    createdAt: new Date(),
    retryCount: 0
  })
  
  yield* scheduler.scheduleUrgentTask({
    id: "security-alert",
    priority: "urgent",
    execute: () => Effect.succeed(console.log("Processing security alert")),
    createdAt: new Date(),
    retryCount: 0
  })
  
  // Check queue status
  const status = yield* scheduler.getQueueStatus()
  console.log("Queue status:", status)
})

Example 3: Undo/Redo System for Document Editor

Implementing an efficient undo/redo system that manages document state changes without expensive memory copies:

import { MutableList, Effect, Option } from "effect"

interface DocumentChange {
  id: string
  type: "insert" | "delete" | "replace"
  position: number
  content: string
  previousContent?: string
  timestamp: Date
}

interface DocumentState {
  content: string
  cursorPosition: number
  version: number
}

class DocumentUndoRedoManager {
  private undoStack = MutableList.empty<DocumentChange>()
  private redoStack = MutableList.empty<DocumentChange>()
  private currentState: DocumentState
  private maxHistorySize: number
  
  constructor(initialContent: string = "", maxHistorySize: number = 100) {
    this.currentState = {
      content: initialContent,
      cursorPosition: 0,
      version: 0
    }
    this.maxHistorySize = maxHistorySize
  }
  
  // O(1) - Add change to undo stack
  recordChange(change: DocumentChange): Effect.Effect<void> {
    return Effect.gen(function* () {
      // Clear redo stack when new change is made
      MutableList.reset(this.redoStack)
      
      // Add to undo stack
      MutableList.append(this.undoStack, change)
      
      // Maintain history size limit
      if (MutableList.length(this.undoStack) > this.maxHistorySize) {
        MutableList.shift(this.undoStack) // Remove oldest
      }
      
      // Apply change to current state
      yield* this.applyChange(change)
    }.bind(this))
  }
  
  // O(1) - Undo last change
  undo(): Effect.Effect<Option.Option<DocumentState>> {
    return Effect.gen(function* () {
      const lastChange = MutableList.pop(this.undoStack)
      
      if (!lastChange) {
        return Option.none()
      }
      
      // Move change to redo stack
      MutableList.append(this.redoStack, lastChange)
      
      // Reverse the change
      yield* this.reverseChange(lastChange)
      
      return Option.some({ ...this.currentState })
    }.bind(this))
  }
  
  // O(1) - Redo last undone change
  redo(): Effect.Effect<Option.Option<DocumentState>> {
    return Effect.gen(function* () {
      const lastUndone = MutableList.pop(this.redoStack)
      
      if (!lastUndone) {
        return Option.none()
      }
      
      // Move back to undo stack
      MutableList.append(this.undoStack, lastUndone)
      
      // Reapply the change
      yield* this.applyChange(lastUndone)
      
      return Option.some({ ...this.currentState })
    }.bind(this))
  }
  
  private applyChange(change: DocumentChange): Effect.Effect<void> {
    return Effect.gen(function* () {
      const { content } = this.currentState
      
      switch (change.type) {
        case "insert":
          this.currentState.content = 
            content.slice(0, change.position) + 
            change.content + 
            content.slice(change.position)
          this.currentState.cursorPosition = change.position + change.content.length
          break
          
        case "delete":
          this.currentState.content = 
            content.slice(0, change.position) + 
            content.slice(change.position + change.content.length)
          this.currentState.cursorPosition = change.position
          break
          
        case "replace":
          this.currentState.content = 
            content.slice(0, change.position) + 
            change.content + 
            content.slice(change.position + (change.previousContent?.length || 0))
          this.currentState.cursorPosition = change.position + change.content.length
          break
      }
      
      this.currentState.version++
    }.bind(this))
  }
  
  private reverseChange(change: DocumentChange): Effect.Effect<void> {
    return Effect.gen(function* () {
      switch (change.type) {
        case "insert":
          // Reverse insert by deleting
          yield* this.applyChange({
            ...change,
            type: "delete",
            content: change.content
          })
          break
          
        case "delete":
          // Reverse delete by inserting
          yield* this.applyChange({
            ...change,
            type: "insert",
            content: change.content
          })
          break
          
        case "replace":
          // Reverse replace by restoring previous content
          yield* this.applyChange({
            ...change,
            type: "replace",
            content: change.previousContent || "",
            previousContent: change.content
          })
          break
      }
    }.bind(this))
  }
  
  // Batch operations for complex edits
  recordBatchChanges(changes: DocumentChange[]): Effect.Effect<void> {
    return Effect.gen(function* () {
      // Create a composite change for undo purposes
      const batchChange: DocumentChange = {
        id: crypto.randomUUID(),
        type: "replace",
        position: Math.min(...changes.map(c => c.position)),
        content: this.currentState.content, // Will be updated after applying all changes
        previousContent: this.currentState.content,
        timestamp: new Date()
      }
      
      // Apply all changes
      for (const change of changes) {
        yield* this.applyChange(change)
      }
      
      // Update batch change with final content
      batchChange.content = this.currentState.content
      
      // Record the batch as a single undoable operation
      MutableList.append(this.undoStack, batchChange)
      MutableList.reset(this.redoStack)
      
      if (MutableList.length(this.undoStack) > this.maxHistorySize) {
        MutableList.shift(this.undoStack)
      }
    }.bind(this))
  }
  
  // Get history information
  getHistoryInfo(): Effect.Effect<{
    canUndo: boolean
    canRedo: boolean
    undoCount: number
    redoCount: number
    currentVersion: number
  }> {
    return Effect.succeed({
      canUndo: !MutableList.isEmpty(this.undoStack),
      canRedo: !MutableList.isEmpty(this.redoStack),
      undoCount: MutableList.length(this.undoStack),
      redoCount: MutableList.length(this.redoStack),
      currentVersion: this.currentState.version
    })
  }
  
  getCurrentState(): DocumentState {
    return { ...this.currentState }
  }
  
  // Clear all history
  clearHistory(): Effect.Effect<void> {
    return Effect.gen(function* () {
      MutableList.reset(this.undoStack)
      MutableList.reset(this.redoStack)
    }.bind(this))
  }
}

// Usage in document editor
const documentEditorExample = Effect.gen(function* () {
  const undoRedoManager = new DocumentUndoRedoManager("Hello World")
  
  // User types some text
  yield* undoRedoManager.recordChange({
    id: "1",
    type: "insert",
    position: 11,
    content: "!",
    timestamp: new Date()
  })
  
  // User deletes some text
  yield* undoRedoManager.recordChange({
    id: "2",
    type: "delete",
    position: 6,
    content: "World",
    timestamp: new Date()
  })
  
  console.log("Current state:", undoRedoManager.getCurrentState())
  
  // Undo the last change
  const undoResult = yield* undoRedoManager.undo()
  if (Option.isSome(undoResult)) {
    console.log("After undo:", undoResult.value)
  }
  
  // Check what operations are available
  const historyInfo = yield* undoRedoManager.getHistoryInfo()
  console.log("History info:", historyInfo)
})

Advanced Features Deep Dive

Feature 1: Memory-Efficient Iterator Pattern

MutableList implements JavaScript's Iterable protocol, providing efficient iteration without creating intermediate arrays:

Basic Iterator Usage

import { MutableList } from "effect"

const processLogEntries = (entries: MutableList<LogEntry>): void => {
  // Direct iteration - no memory allocation for intermediate arrays
  for (const entry of entries) {
    if (entry.level === "ERROR") {
      alertOnError(entry)
    }
  }
}

// Memory-efficient processing of large datasets
const analyzeMetrics = (metrics: MutableList<Metric>): MetricSummary => {
  let sum = 0
  let count = 0
  let max = Number.MIN_SAFE_INTEGER
  let min = Number.MAX_SAFE_INTEGER
  
  // O(n) time, O(1) space - no array copies
  for (const metric of metrics) {
    sum += metric.value
    count += 1
    max = Math.max(max, metric.value)
    min = Math.min(min, metric.value)
  }
  
  return {
    average: sum / count,
    total: sum,
    count,
    max,
    min
  }
}

Real-World Iterator Example

// Streaming data processor using MutableList
class StreamingDataProcessor<T> {
  private buffer = MutableList.empty<T>()
  private readonly bufferSize: number
  
  constructor(bufferSize: number = 1000) {
    this.bufferSize = bufferSize
  }
  
  addData(item: T): Effect.Effect<void> {
    return Effect.gen(function* () {
      MutableList.append(this.buffer, item)
      
      // Process in chunks when buffer is full
      if (MutableList.length(this.buffer) >= this.bufferSize) {
        yield* this.processBufferChunk()
      }
    }.bind(this))
  }
  
  private processBufferChunk(): Effect.Effect<void> {
    return Effect.gen(function* () {
      const processed: T[] = []
      
      // Efficient iteration without array conversion
      for (const item of this.buffer) {
        const processedItem = yield* this.processItem(item)
        processed.push(processedItem)
      }
      
      // Send processed chunk
      yield* this.sendProcessedChunk(processed)
      
      // Clear buffer for next chunk
      MutableList.reset(this.buffer)
    }.bind(this))
  }
  
  private processItem(item: T): Effect.Effect<T> {
    // Placeholder for item processing logic
    return Effect.succeed(item)
  }
  
  private sendProcessedChunk(chunk: T[]): Effect.Effect<void> {
    // Placeholder for sending processed data
    return Effect.succeed(undefined)
  }
}

Feature 2: Advanced Memory Management

MutableList provides efficient memory management through strategic reset and reuse patterns:

Memory Pool Pattern

import { MutableList, Effect } from "effect"

// Reusable buffer pool to minimize garbage collection
class MutableListPool<T> {
  private pool = MutableList.empty<MutableList<T>>()
  private readonly maxPoolSize: number
  
  constructor(maxPoolSize: number = 10) {
    this.maxPoolSize = maxPoolSize
  }
  
  // O(1) - Get or create a list
  acquire(): MutableList<T> {
    const pooled = MutableList.shift(this.pool)
    return pooled || MutableList.empty<T>()
  }
  
  // O(1) - Return list to pool
  release(list: MutableList<T>): void {
    if (MutableList.length(this.pool) < this.maxPoolSize) {
      MutableList.reset(list) // Clear contents but keep structure
      MutableList.append(this.pool, list)
    }
    // If pool is full, let GC handle the list
  }
  
  // Create scoped list usage
  withList<R>(operation: (list: MutableList<T>) => Effect.Effect<R>): Effect.Effect<R> {
    return Effect.gen(function* () {
      const list = this.acquire()
      
      try {
        const result = yield* operation(list)
        return result
      } finally {
        this.release(list)
      }
    }.bind(this))
  }
}

// Usage in high-throughput scenarios
const processHighVolumeData = Effect.gen(function* () {
  const listPool = new MutableListPool<DataPoint>(5)
  
  const processDataBatch = (batch: DataPoint[]) =>
    listPool.withList(list => Effect.gen(function* () {
      // Fill list with batch data
      for (const dataPoint of batch) {
        MutableList.append(list, dataPoint)
      }
      
      // Process efficiently
      const results: ProcessedData[] = []
      for (const point of list) {
        const processed = yield* processDataPoint(point)
        results.push(processed)
      }
      
      return results
      // List automatically returned to pool when scope exits
    }))
  
  // Process multiple batches reusing pooled lists
  for (let i = 0; i < 100; i++) {
    const batch = yield* getBatchData(i)
    const results = yield* processDataBatch(batch)
    yield* saveResults(results)
  }
})

Advanced Resource Management

// Resource-aware list management
class ResourceManagedList<T> {
  private list = MutableList.empty<T>()
  private memoryUsage = 0
  private readonly maxMemoryMB: number
  
  constructor(maxMemoryMB: number = 100) {
    this.maxMemoryMB = maxMemoryMB
  }
  
  addItem(item: T, estimatedSizeBytes: number): Effect.Effect<boolean> {
    return Effect.gen(function* () {
      const estimatedSizeMB = estimatedSizeBytes / (1024 * 1024)
      
      if (this.memoryUsage + estimatedSizeMB > this.maxMemoryMB) {
        // Try to free space by removing old items
        const freed = yield* this.freeMemory(estimatedSizeMB)
        
        if (!freed) {
          return false // Cannot add item
        }
      }
      
      MutableList.append(this.list, item)
      this.memoryUsage += estimatedSizeMB
      return true
    }.bind(this))
  }
  
  private freeMemory(requiredMB: number): Effect.Effect<boolean> {
    return Effect.gen(function* () {
      let freed = 0
      let removedCount = 0
      
      // Remove from front (oldest items) until we have enough space
      while (freed < requiredMB && !MutableList.isEmpty(this.list)) {
        const removed = MutableList.shift(this.list)
        if (removed) {
          // Estimate freed memory (simplified)
          freed += this.estimateItemSize(removed) / (1024 * 1024)
          removedCount++
        }
      }
      
      this.memoryUsage -= freed
      
      if (removedCount > 0) {
        console.log(`Freed ${freed.toFixed(2)}MB by removing ${removedCount} items`)
      }
      
      return freed >= requiredMB
    }.bind(this))
  }
  
  private estimateItemSize(item: T): number {
    // Simplified size estimation
    return JSON.stringify(item).length * 2 // Rough estimate for JS object overhead
  }
  
  getMemoryInfo(): { usageMB: number; itemCount: number; maxMB: number } {
    return {
      usageMB: this.memoryUsage,
      itemCount: MutableList.length(this.list),
      maxMB: this.maxMemoryMB
    }
  }
}

Feature 3: Performance Optimization Patterns

Leveraging MutableList's O(1) operations for maximum efficiency:

Efficient Data Structure Transformations

// Converting between data structures efficiently
class DataStructureConverter {
  
  // Array to MutableList - O(n) but single pass
  static arrayToMutableList<T>(array: readonly T[]): MutableList<T> {
    return MutableList.fromIterable(array)
  }
  
  // MutableList to Array - O(n) using built-in iterator
  static mutableListToArray<T>(list: MutableList<T>): T[] {
    return Array.from(list)
  }
  
  // Merge multiple MutableLists efficiently
  static mergeLists<T>(...lists: MutableList<T>[]): MutableList<T> {
    const result = MutableList.empty<T>()
    
    for (const list of lists) {
      // O(n) for each list - append each element
      MutableList.forEach(list, item => MutableList.append(result, item))
    }
    
    return result
  }
  
  // Split MutableList at position - O(n) but efficient
  static splitAt<T>(list: MutableList<T>, position: number): [MutableList<T>, MutableList<T>] {
    const left = MutableList.empty<T>()
    const right = MutableList.empty<T>()
    
    let index = 0
    for (const item of list) {
      if (index < position) {
        MutableList.append(left, item)
      } else {
        MutableList.append(right, item)
      }
      index++
    }
    
    return [left, right]
  }
  
  // Partition based on predicate
  static partition<T>(
    list: MutableList<T>, 
    predicate: (item: T) => boolean
  ): [MutableList<T>, MutableList<T>] {
    const truthyItems = MutableList.empty<T>()
    const falsyItems = MutableList.empty<T>()
    
    for (const item of list) {
      if (predicate(item)) {
        MutableList.append(truthyItems, item)
      } else {
        MutableList.append(falsyItems, item)
      }
    }
    
    return [truthyItems, falsyItems]
  }
}

// Performance-optimized batch operations
const performBatchOperations = Effect.gen(function* () {
  const sourceData = Array.from({ length: 10000 }, (_, i) => ({ id: i, value: Math.random() }))
  
  // Convert to MutableList once
  const dataList = DataStructureConverter.arrayToMutableList(sourceData)
  
  // Efficient filtering and partitioning
  const [highValue, lowValue] = DataStructureConverter.partition(
    dataList,
    item => item.value > 0.5
  )
  
  console.log(`High value items: ${MutableList.length(highValue)}`)
  console.log(`Low value items: ${MutableList.length(lowValue)}`)
  
  // Process each partition efficiently
  MutableList.forEach(highValue, item => {
    // Process high-value items
    processHighValueItem(item)
  })
  
  MutableList.forEach(lowValue, item => {
    // Process low-value items
    processLowValueItem(item)
  })
})

Practical Patterns & Best Practices

Pattern 1: Efficient Queue Implementation

import { MutableList, Effect, Option } from "effect"

// Generic queue with O(1) operations
class EfficiientQueue<T> {
  private items = MutableList.empty<T>()
  
  // O(1) - Add to back of queue
  enqueue(item: T): void {
    MutableList.append(this.items, item)
  }
  
  // O(1) - Remove from front of queue
  dequeue(): Option.Option<T> {
    const item = MutableList.shift(this.items)
    return item ? Option.some(item) : Option.none()
  }
  
  // O(1) - Peek at front without removing
  peek(): Option.Option<T> {
    return Option.fromNullable(MutableList.head(this.items))
  }
  
  // O(1) - Check if empty
  isEmpty(): boolean {
    return MutableList.isEmpty(this.items)
  }
  
  // O(1) - Get size
  size(): number {
    return MutableList.length(this.items)
  }
  
  // O(n) - Process all items without removing
  forEach(callback: (item: T) => void): void {
    MutableList.forEach(this.items, callback)
  }
  
  // O(1) - Clear all items
  clear(): void {
    MutableList.reset(this.items)
  }
}

// Priority queue using multiple MutableLists
class PriorityQueue<T> {
  private highPriority = MutableList.empty<T>()
  private normalPriority = MutableList.empty<T>()
  private lowPriority = MutableList.empty<T>()
  
  enqueue(item: T, priority: "high" | "normal" | "low" = "normal"): void {
    switch (priority) {
      case "high":
        MutableList.append(this.highPriority, item)
        break
      case "normal":
        MutableList.append(this.normalPriority, item)
        break
      case "low":
        MutableList.append(this.lowPriority, item)
        break
    }
  }
  
  dequeue(): Option.Option<T> {
    // Process high priority first
    let item = MutableList.shift(this.highPriority)
    if (item) return Option.some(item)
    
    // Then normal priority
    item = MutableList.shift(this.normalPriority)
    if (item) return Option.some(item)
    
    // Finally low priority
    item = MutableList.shift(this.lowPriority)
    return item ? Option.some(item) : Option.none()
  }
  
  getStatus(): { high: number; normal: number; low: number; total: number } {
    return {
      high: MutableList.length(this.highPriority),
      normal: MutableList.length(this.normalPriority),
      low: MutableList.length(this.lowPriority),
      total: MutableList.length(this.highPriority) + 
             MutableList.length(this.normalPriority) + 
             MutableList.length(this.lowPriority)
    }
  }
}

Pattern 2: Efficient Stack Implementation

// Stack implementation with O(1) operations
class EfficientStack<T> {
  private items = MutableList.empty<T>()
  
  // O(1) - Push to end (top of stack)
  push(item: T): void {
    MutableList.append(this.items, item)
  }
  
  // O(1) - Pop from end (top of stack)
  pop(): Option.Option<T> {
    const item = MutableList.pop(this.items)
    return item ? Option.some(item) : Option.none()
  }
  
  // O(1) - Peek at top without removing
  peek(): Option.Option<T> {
    return Option.fromNullable(MutableList.tail(this.items))
  }
  
  isEmpty(): boolean {
    return MutableList.isEmpty(this.items)
  }
  
  size(): number {
    return MutableList.length(this.items)
  }
  
  clear(): void {
    MutableList.reset(this.items)
  }
}

// Call stack tracker for debugging
class CallStackTracker {
  private stack = new EfficientStack<{ function: string; timestamp: Date; args: unknown[] }>()
  
  enterFunction(functionName: string, ...args: unknown[]): Effect.Effect<void> {
    return Effect.sync(() => {
      this.stack.push({
        function: functionName,
        timestamp: new Date(),
        args
      })
    })
  }
  
  exitFunction(): Effect.Effect<Option.Option<string>> {
    return Effect.sync(() => {
      const call = this.stack.pop()
      return Option.map(call, c => c.function)
    })
  }
  
  getCurrentCallStack(): Effect.Effect<string[]> {
    return Effect.sync(() => {
      const calls: string[] = []
      this.stack.forEach(call => calls.unshift(call.function)) // Reverse order for stack trace
      return calls
    })
  }
  
  getStackDepth(): number {
    return this.stack.size()
  }
}

Pattern 3: Circular Buffer Implementation

// Fixed-size circular buffer using MutableList
class CircularBuffer<T> {
  private items = MutableList.empty<T>()
  private readonly maxSize: number
  
  constructor(maxSize: number) {
    this.maxSize = maxSize
  }
  
  // O(1) - Add item, removing oldest if at capacity
  add(item: T): Option.Option<T> {
    let removed: Option.Option<T> = Option.none()
    
    if (MutableList.length(this.items) >= this.maxSize) {
      const oldestItem = MutableList.shift(this.items)
      removed = oldestItem ? Option.some(oldestItem) : Option.none()
    }
    
    MutableList.append(this.items, item)
    return removed
  }
  
  // Get all items in order (oldest to newest)
  getItems(): T[] {
    return Array.from(this.items)
  }
  
  // Get latest N items
  getLatest(count: number): T[] {
    const allItems = Array.from(this.items)
    return allItems.slice(-count)
  }
  
  // Get oldest N items
  getOldest(count: number): T[] {
    const result: T[] = []
    let collected = 0
    
    for (const item of this.items) {
      if (collected >= count) break
      result.push(item)
      collected++
    }
    
    return result
  }
  
  isFull(): boolean {
    return MutableList.length(this.items) >= this.maxSize
  }
  
  clear(): void {
    MutableList.reset(this.items)
  }
}

// Usage for metrics collection
const metricsCollector = Effect.gen(function* () {
  const metricsBuffer = new CircularBuffer<{ timestamp: Date; value: number }>(1000)
  
  // Continuously collect metrics
  for (let i = 0; i < 1500; i++) {
    const metric = { timestamp: new Date(), value: Math.random() * 100 }
    const evicted = metricsBuffer.add(metric)
    
    if (Option.isSome(evicted)) {
      // Log evicted old metric if needed
      console.log(`Evicted old metric from ${evicted.value.timestamp}`)
    }
    
    yield* Effect.sleep(10) // Simulate time passing
  }
  
  // Get latest 100 metrics for analysis
  const recentMetrics = metricsBuffer.getLatest(100)
  console.log(`Analyzed ${recentMetrics.length} recent metrics`)
})

Integration Examples

Integration with Effect Streams

import { MutableList, Effect, Stream } from "effect"

// Buffer Stream chunks efficiently
const streamBufferExample = Effect.gen(function* () {
  const buffer = MutableList.empty<number>()
  
  // Create a stream that processes items in batches
  const processedStream = Stream.fromIterable([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]).pipe(
    Stream.tap(item => Effect.sync(() => MutableList.append(buffer, item))),
    Stream.groupedWithin(3, "1 second"), // Group into chunks
    Stream.tap(chunk => 
      Effect.sync(() => {
        console.log(`Processing chunk of ${chunk.length} items`)
        // Process the chunk using buffer contents
        const bufferArray = Array.from(buffer)
        console.log(`Buffer contains: ${bufferArray}`)
        
        // Clear buffer after processing
        MutableList.reset(buffer)
      })
    )
  )
  
  // Run the stream
  yield* Stream.runDrain(processedStream)
})

// Stream to MutableList collector
const streamCollector = <T>(stream: Stream.Stream<T>): Effect.Effect<MutableList<T>> =>
  Effect.gen(function* () {
    const collected = MutableList.empty<T>()
    
    yield* Stream.runForEach(stream, item =>
      Effect.sync(() => MutableList.append(collected, item))
    )
    
    return collected
  })

Integration with Testing Frameworks

import { MutableList, Effect, TestClock, TestContext } from "effect"

// Test helper for MutableList operations
const testMutableListOperations = Effect.gen(function* () {
  const list = MutableList.empty<string>()
  
  // Test append operations
  MutableList.append(list, "first")
  MutableList.append(list, "second")
  MutableList.append(list, "third")
  
  // Verify state
  const length = MutableList.length(list)
  const head = MutableList.head(list)
  const tail = MutableList.tail(list)
  
  console.assert(length === 3, "Length should be 3")
  console.assert(head === "first", "Head should be 'first'")
  console.assert(tail === "third", "Tail should be 'third'")
  
  // Test pop operation
  const popped = MutableList.pop(list)
  console.assert(popped === "third", "Popped item should be 'third'")
  console.assert(MutableList.length(list) === 2, "Length should be 2 after pop")
  
  // Test shift operation
  const shifted = MutableList.shift(list)
  console.assert(shifted === "first", "Shifted item should be 'first'")
  console.assert(MutableList.length(list) === 1, "Length should be 1 after shift")
  
  console.log("All MutableList tests passed!")
})

// Property-based testing helper
const testMutableListProperties = Effect.gen(function* () {
  const list = MutableList.empty<number>()
  
  // Test that append then pop gives same item
  const testItem = 42
  MutableList.append(list, testItem)
  const popped = MutableList.pop(list)
  console.assert(popped === testItem, "Append then pop should return same item")
  
  // Test that prepend then shift gives same item
  MutableList.prepend(list, testItem)
  const shifted = MutableList.shift(list)
  console.assert(shifted === testItem, "Prepend then shift should return same item")
  
  // Test length consistency
  const initialLength = MutableList.length(list)
  MutableList.append(list, 1)
  MutableList.append(list, 2)
  MutableList.append(list, 3)
  console.assert(
    MutableList.length(list) === initialLength + 3,
    "Length should increase by number of appends"
  )
  
  console.log("All property tests passed!")
})

Integration with JSON and Serialization

// Serialization helpers for MutableList
class MutableListSerializer {
  static toJSON<T>(list: MutableList<T>): T[] {
    return Array.from(list)
  }
  
  static fromJSON<T>(data: T[]): MutableList<T> {
    return MutableList.fromIterable(data)
  }
  
  static stringify<T>(list: MutableList<T>): string {
    return JSON.stringify(this.toJSON(list))
  }
  
  static parse<T>(json: string): MutableList<T> {
    const data = JSON.parse(json) as T[]
    return this.fromJSON(data)
  }
}

// Usage in data persistence
const dataPersistenceExample = Effect.gen(function* () {
  const taskList = MutableList.empty<{ id: string; title: string; completed: boolean }>()
  
  // Add some tasks
  MutableList.append(taskList, { id: "1", title: "Learn Effect", completed: false })
  MutableList.append(taskList, { id: "2", title: "Build app", completed: false })
  MutableList.append(taskList, { id: "3", title: "Deploy", completed: false })
  
  // Serialize to JSON
  const serialized = MutableListSerializer.stringify(taskList)
  console.log("Serialized:", serialized)
  
  // Save to storage (simulated)
  yield* Effect.succeed(localStorage.setItem("tasks", serialized))
  
  // Load from storage
  const loaded = yield* Effect.succeed(localStorage.getItem("tasks"))
  if (loaded) {
    const deserializedList = MutableListSerializer.parse(loaded)
    console.log("Loaded tasks count:", MutableList.length(deserializedList))
    
    // Verify data integrity
    MutableList.forEach(deserializedList, task => {
      console.log(`Task: ${task.title} (${task.completed ? 'done' : 'pending'})`)
    })
  }
})

Conclusion

MutableList provides efficient O(1) insertion and deletion operations at both ends of a doubly-linked list, making it ideal for scenarios requiring frequent modifications without the overhead of array shifting.

Key benefits:

• Performance: O(1) operations for head/tail insertion, deletion, and access
• Memory Efficiency: No need to copy or shift elements during modifications
• Iterator Support: Seamless integration with JavaScript iteration protocols
• Mutation Optimization: Designed for scenarios where mutation is preferred over immutability

MutableList is particularly valuable for implementing queues, stacks, undo systems, streaming buffers, and any application requiring efficient insertion and removal operations at list boundaries.