Stack implementation in Clojure II - A functional approach

Submitted by viksit on Thu, 06/03/2010 - 23:07

My last post on the topic was creating a stack implementation using Clojure protocols and records - except, it used atoms internally and wasn't inherently "functional".

Here's my take on a new implementation that builds on the existing protocol and internally, always returns a new stack keeping the original one unmodified. Comments welcome!

(ns viksit-stack
  (:refer-clojure :exclude [pop]))

(defprotocol PStack
  "A stack protocol"
  (push [this val] "Push element in")
  (pop [this] "Pop element from stack")
  (top [this] "Get top element from stack"))

; A functional stack record that uses immutable semantics
; It returns a copy of the datastructure while ensuring the original
; is not affected.
(defrecord FStack [coll]
  PStack
  (push [_ val]
        "Return the stack with the new element inserted"
        (FStack. (conj coll val)))
  (pop [_]
       "Return the stack without the top element"
         (FStack. (rest coll)))
  (top [_]
       "Return the top value of the stack"
       (first coll)))

; The funtional stack can be used in conjunction with a ref or atom

viksit-stack> (def s2 (atom (FStack. '())))
#'viksit-stack/s2
viksit-stack> s2
#<Atom@69af0fcf: #:viksit-stack.FStack{:coll ()}>
viksit-stack> (swap! s2 push 10)
#:viksit-stack.FStack{:coll (10)}
viksit-stack> (swap! s2 push 20)
#:viksit-stack.FStack{:coll (20 10)}
viksit-stack> (swap! s2 pop)
#:viksit-stack.FStack{:coll (10)}
viksit-stack> (top @s2)
10