Functional programming is becoming more and more popular these days, especially given the use of multi-core and distributed architectures. A purely functional data structure is thread safe in nature and it can be easily shared across threads or used for low-cost large scale parallel programming. And Clojure is one of the functional languages that really shines.
Different programming styles have different objectives; Clojure focuses on solving practical problems. Programmers can easily switch between strict and lazy evaluation, immutable data structures and mutable ones. Because there's no silver bullet to solve parallel programming problems, a luxury that Clojure programmer has, is that he can combine all the goodies from different parts of the world and make great use of it. In order to demonstrate the flexibility of Clojure, we'll build a persistent queue as both strict data structure and in lazy evaluated flavor.
Strict Persistent Queue
A strict persistent queue is formed by two list: front and rear; the element is enqueued at the rear, and dequeued at the front. After doing the enqueue/dequeue operation, the queue has to balance its internal data structure; If the front list is empty, reverse the rear list and append it to the front.
(defn queue-balance [[f r :as this]]
(if (empty? f)
[(reverse r) '()]
this))
(defn q-head [[[x & f] _]] x)
(defn q-tail [[[x & f] r]] (queue-balance [f r]))
(defn q-snoc [[f r] x] (queue-balance [f (cons x r)]))
We can try this on REPL:
user> (reduce q-snoc [nil nil] (range 1 10)) [(1) (9 8 7 6 5 4 3 2)] user> (q-head (reduce q-snoc [nil nil] (range 1 10))) 1 user> (q-tail (reduce q-snoc [nil nil] (range 1 10))) [(2 3 4 5 6 7 8 9) ()] ;; balanced
However, what if other thread also want to read (q-tail ...)? An unnecessary calculation on (queue-balance .. is a waste. No worries, given that this is a purely functional data structure, all the returned results only depend on the input, and we can cache the input-output map in a memoize function:
(def queue-balance
(memoize (fn [[f r :as this]]
(println this) ;; print if not cached
(if (empty? f)
[(reverse r) '()]
this))))
user> (q-tail (reduce q-snoc [nil nil] (range 1 9))) [nil (1)] [(1) (2)] [(1) (3 2)] [(1) (4 3 2)] [(1) (5 4 3 2)] [(1) (6 5 4 3 2)] [(1) (7 6 5 4 3 2)] [(1) (8 7 6 5 4 3 2)] [nil (8 7 6 5 4 3 2)] [(2 3 4 5 6 7 8) ()] user> (q-tail (reduce q-snoc [nil nil] (range 1 9))) [(2 3 4 5 6 7 8) ()]
Lazy Persistent Queue
Clojure code evaluation and data structures (lists, persistent array, persistent map, etc.) are strict, but most of the utility functions return lazy sequences. Here we are going to use two of these functions lazy-cat and rest. lazy-cat takes two or more sequences, yields a lazy sequence, and returns the concatenation of the sequences. rest take a sequence and returns the lazy sequence of the items after the first.
Instead of reversing the rear sequence and appending to the front when the front list is empty, we can reverse the list when rear list count is greater than one in the front. Thus the peak calculation of reverse is separated to parts. Here is the implementation:
(def lazy-queue
(memoize (fn [[f len-f r len-r :as q]]
(println q)
(if (<= len-r len-f) q
[(lazy-cat f (reverse r)) (+ len-f len-r) '() 0]))))
(defn lazy-snoc [[f len-f r len-r :as q] x]
(lazy-queue [f len-f (cons x r) (inc len-r)]))
(defn lazy-head [[f & _]] (first f))
(defn lazy-tail [[f len-f r len-r]]
(lazy-queue [(rest f) (dec len-f) r len-r]))
Applying memoize to lazily evaluated version is also trivial, just use the function to wrap the actual body. The calculation would be something like this:
user> (def q (reduce lazy-snoc [nil 0 nil 0] (range 15))) [nil 0 (0) 1] [(0) 1 (1) 1] [(0) 1 (2 1) 2] [(0 1 2) 3 (3) 1] [(0 1 2) 3 (4 3) 2] [(0 1 2) 3 (5 4 3) 3] [(0 1 2) 3 (6 5 4 3) 4] [(0 1 2 3 4 5 6) 7 (7) 1] [(0 1 2 3 4 5 6) 7 (8 7) 2] [(0 1 2 3 4 5 6) 7 (9 8 7) 3] [(0 1 2 3 4 5 6) 7 (10 9 8 7) 4] [(0 1 2 3 4 5 6) 7 (11 10 9 8 7) 5] [(0 1 2 3 4 5 6) 7 (12 11 10 9 8 7) 6] [(0 1 2 3 4 5 6) 7 (13 12 11 10 9 8 7) 7] [(0 1 2 3 4 5 6) 7 (14 13 12 11 10 9 8 7) 8] #'user/q user> (def q (reduce lazy-snoc [nil 0 nil 0] (range 15))) #'user/q user> (lazy-head q) ;; cached 0 user> (lazy-head (lazy-tail q)) [(1 2 3 4 5 6 7 8 9 10 11 12 13 14) 14 () 0] user> (lazy-head (lazy-tail q)) ;; cached 1
Although Clojure itself has a Persistent Queue, implemented in Java, the idea is the same. Functional structures can not be only applied to inter-thread or inter-process data sharing, but also to distributed data architectures (especially interesting challenges are in dealing with large-scale data stores). For getting deeper into the subject, we recommend reading "Purely Functional Data Structures" by Chris Okasaki.
