Clojure Is Awesome!!! [PART 15]

Mastering Deques Welcome back to Clojure Is Awesome! In Part 15, we’re diving into the Deque (double-ended queue)—a data structure that shines with its ability to add or remove elements from both ends. While Clojure doesn’t ship with a built-in Deque, we’ll craft one today using protocols and records, bridging the gap between object-oriented roots and functional elegance. This isn’t just about slapping code together—it’s about building something cohesive, extensible, and idiomatic. We’ll explore what a Deque is, why it matters, and how we can implement it in Clojure with clean, functional principles. Expect practical examples, a bit of code dissection, and some inspiration for your next project. What is a Deque, and Why Does It Matter? A Deque is a double-ended queue—a generalization of stacks and queues. It supports four key operations: Add to the front (push-front). Add to the back (push-back). Remove from the front (pop-front). Remove from the back (pop-back). This flexibility makes Deques a go-to in scenarios like: Task Scheduling: Prioritize urgent tasks at the front, routine ones at the back. Undo/Redo Systems: Track state changes with access to both ends. Sliding Windows: Manage dynamic ranges in algorithms. In OOP languages like Java (ArrayDeque) or Python (collections.deque), Deques are mutable and optimized for speed. In Clojure, we’ll lean on immutability and persistence, using protocols to define the behavior and records to encapsulate the data. The result? A functional Deque that’s safe, composable, and ready for action. Implementing a Deque Our Deque will live as a VectorDeque record, backed by a persistent vector, and adhere to a Deque protocol. (ns clojure-is-awesome.deque (:require [clojure.spec.alpha :as s])) (defprotocol Deque "A protocol defining double-ended queue operations." (push-front [this element] "Adds an element to the front. Returns a new deque.") (push-back [this element] "Adds an element to the back. Returns a new deque.") (pop-front [this] "Removes and returns the front element and new deque as a map {:element, :deque}.") (pop-back [this] "Removes and returns the back element and new deque as a map {:element, :deque}.") (peek-front [this] "Returns the front element without removing it, or nil if empty.") (peek-back [this] "Returns the back element without removing it, or nil if empty.") (deque-size [this] "Returns the number of elements in the deque.")) ;; Record Definition (defrecord VectorDeque [elements] Deque (push-front [_ element] (VectorDeque. (into [element] elements))) (push-back [_ element] (VectorDeque. (conj elements element))) (pop-front [_] (if (empty? elements) {:element nil :deque (VectorDeque. elements)} {:element (first elements) :deque (VectorDeque. (vec (rest elements)))})) (pop-back [_] (if (empty? elements) {:element nil :deque (VectorDeque. elements)} {:element (peek elements) :deque (VectorDeque. (pop elements))})) (peek-front [_] (first elements)) (peek-back [_] (peek elements)) (deque-size [_] (count elements))) (defn create-deque "Creates an empty deque implemented as a VectorDeque. Returns: A new VectorDeque instance." [] (VectorDeque. [])) (s/def ::elements vector?) (s/def ::deque (s/keys :req-un [::elements])) (s/def ::element any?) Now, let's see it in action: (def my-deque (-> (create-deque) (push-back 1) (push-back 2) (push-front 0))) (println "Deque:" (:elements my-deque)) ;; Deque: [0 1 2] (println "Front:" (peek-front my-deque)) ;; Front: 0 (println "Back:" (peek-back my-deque)) ;; Back: 2 (println "Size:" (deque-size my-deque)) ;; Size: 3 (def front-result (pop-front my-deque)) (println "Popped front:" (:element front-result)) ;; Popped front: 0 (println "New deque:" (:elements (:deque front-result))) ;; New deque: [1 2] Works like a charm! The operations are now tied to our VectorDeque, feeling more unified. Practical Use Case: A Task Scheduler Let’s put our Deque to work with a task scheduler—high-priority tasks go to the front, low-priority to the back: (defn schedule-task "Schedules a task in the deque based on priority. Args: deque - A Deque implementation (e.g., VectorDeque). task - A map with :name and :priority. Returns: A new deque with the task added." [deque {:keys [priority] :as task}] (if (= priority :high) (push-front deque task) (push-back deque task))) (defn process-next-task "Processes the next task from the front of the deque. Args: deque - A Deque implementation. Returns: A map with the processed task and the updated deque." [deque] (pop-front deque)) ;; Usage (def tasks (-> (create-deque) (schedule-task {:name "Send email" :priority :low}) (schedule-t

Mar 16, 2025 - 00:52

Mastering Deques

Welcome back to Clojure Is Awesome! In Part 15, we’re diving into the Deque (double-ended queue)—a data structure that shines with its ability to add or remove elements from both ends. While Clojure doesn’t ship with a built-in Deque, we’ll craft one today using protocols and records, bridging the gap between object-oriented roots and functional elegance. This isn’t just about slapping code together—it’s about building something cohesive, extensible, and idiomatic.

We’ll explore what a Deque is, why it matters, and how we can implement it in Clojure with clean, functional principles. Expect practical examples, a bit of code dissection, and some inspiration for your next project.

What is a Deque, and Why Does It Matter?

A Deque is a double-ended queue—a generalization of stacks and queues. It supports four key operations:

Add to the front (push-front).
Add to the back (push-back).
Remove from the front (pop-front).
Remove from the back (pop-back).

This flexibility makes Deques a go-to in scenarios like:

Task Scheduling: Prioritize urgent tasks at the front, routine ones at the back.
Undo/Redo Systems: Track state changes with access to both ends.
Sliding Windows: Manage dynamic ranges in algorithms.

In OOP languages like Java (ArrayDeque) or Python (collections.deque), Deques are mutable and optimized for speed. In Clojure, we’ll lean on immutability and persistence, using protocols to define the behavior and records to encapsulate the data. The result? A functional Deque that’s safe, composable, and ready for action.

Implementing a Deque

Our Deque will live as a VectorDeque record, backed by a persistent vector, and adhere to a Deque protocol.

(ns clojure-is-awesome.deque
  (:require [clojure.spec.alpha :as s]))

(defprotocol Deque
  "A protocol defining double-ended queue operations."
  (push-front [this element]
    "Adds an element to the front. Returns a new deque.")
  (push-back [this element]
    "Adds an element to the back. Returns a new deque.")
  (pop-front [this]
    "Removes and returns the front element and new deque as a map {:element, :deque}.")
  (pop-back [this]
    "Removes and returns the back element and new deque as a map {:element, :deque}.")
  (peek-front [this]
    "Returns the front element without removing it, or nil if empty.")
  (peek-back [this]
    "Returns the back element without removing it, or nil if empty.")
  (deque-size [this]
    "Returns the number of elements in the deque."))

;; Record Definition
(defrecord VectorDeque [elements]
  Deque
  (push-front [_ element]
    (VectorDeque. (into [element] elements)))

  (push-back [_ element]
    (VectorDeque. (conj elements element)))

  (pop-front [_]
    (if (empty? elements)
      {:element nil :deque (VectorDeque. elements)}
      {:element (first elements) :deque (VectorDeque. (vec (rest elements)))}))

  (pop-back [_]
    (if (empty? elements)
      {:element nil :deque (VectorDeque. elements)}
      {:element (peek elements) :deque (VectorDeque. (pop elements))}))

  (peek-front [_]
    (first elements))

  (peek-back [_]
    (peek elements))

  (deque-size [_]
    (count elements)))

(defn create-deque
  "Creates an empty deque implemented as a VectorDeque.
   Returns:
     A new VectorDeque instance."
  []
  (VectorDeque. []))

(s/def ::elements vector?)
(s/def ::deque (s/keys :req-un [::elements]))
(s/def ::element any?)

Now, let's see it in action:

(def my-deque (-> (create-deque)
                  (push-back 1)
                  (push-back 2)
                  (push-front 0)))

(println "Deque:" (:elements my-deque))    ;; Deque: [0 1 2]
(println "Front:" (peek-front my-deque))   ;; Front: 0
(println "Back:" (peek-back my-deque))     ;; Back: 2
(println "Size:" (deque-size my-deque))    ;; Size: 3

(def front-result (pop-front my-deque))
(println "Popped front:" (:element front-result)) ;; Popped front: 0
(println "New deque:" (:elements (:deque front-result))) ;; New deque: [1 2]

Works like a charm! The operations are now tied to our VectorDeque, feeling more unified.

Practical Use Case: A Task Scheduler

Let’s put our Deque to work with a task scheduler—high-priority tasks go to the front, low-priority to the back:

(defn schedule-task
  "Schedules a task in the deque based on priority.
   Args:
     deque - A Deque implementation (e.g., VectorDeque).
     task - A map with :name and :priority.
   Returns:
     A new deque with the task added."
  [deque {:keys [priority] :as task}]
  (if (= priority :high)
    (push-front deque task)
    (push-back deque task)))

(defn process-next-task
  "Processes the next task from the front of the deque.
   Args:
     deque - A Deque implementation.
   Returns:
     A map with the processed task and the updated deque."
  [deque]
  (pop-front deque))

;; Usage
(def tasks (-> (create-deque)
               (schedule-task {:name "Send email" :priority :low})
               (schedule-task {:name "Fix bug" :priority :high})))

(println "Tasks:" (:elements tasks))
;; Tasks: [{:name "Fix bug" :priority :high} {:name "Send email" :priority :low}]

(def result (process-next-task tasks))
(println "Processed:" (:element result)) ;; Processed: {:name "Fix bug" :priority :high}
(println "Remaining:" (:elements (:deque result))) ;; Remaining: [{:name "Send email" :priority :low}]

This scheduler leverages the Deque’s double-ended nature beautifully, and the protocol keeps it flexible for future tweaks.

Why This Approach Shines

Using protocols and records elevates our Deque from a loose collection of functions to a polished abstraction:

Structure: Operations are bound to VectorDeque, making the intent clear.
Extensibility: Swap in a new Deque implementation without touching the scheduler code.
Functional Goodness: Immutability, purity, and composability are all intact.
Readability: The record’s elements field and protocol methods tell a cohesive story.

Performance-wise, we’re still tied to vectors—O(1) at the back, O(n) at the front. For a truly O(1) Deque, we’d need something like a finger tree, but that’s a tale for another day!

Conclusion

In this Part 15, we’ve taken the Deque concept and given it a functional home in Clojure with protocols and records. It’s more than just a data structure—it’s a showcase of how Clojure blends FP principles with structured design. Whether you’re scheduling tasks, tracking history, or playing with algorithms, this VectorDeque is a trusty companion.

What do you think? Have you used protocols and records to wrangle your own abstractions? Drop your thoughts in the comments—I’d love to hear how you’re making Clojure awesome in your world! Stay tuned for Part 16, where we’ll uncover another gem in Clojure’s treasure chest. Until then, happy coding!