Simple made Easy- A Taste of Clojure for the Cjurious

factorial.clj

(ns factorial)
;;----------------
;;A Simple Problem
;;----------------
;The factorial function can be written as:
;  factorial(n) = 1 * 2 * 3 * ... * n
;
;Let's take the case of factorial(5):
;  1 * 2 * 3 * 4 * 5
;
;which can be expressed in Clojure as:
(* 1 2 3 4 5)
;where * is the multiplication function.
;
;It can also be written as:
(apply * [1 2 3 4 5])
;where [1 2 3 4 5] is a sequence, and 
;apply is a function that applies the 
;given-function to the given-argument-list.
;  (apply f [a b c]) => (f a b c)
;
;We could also write it as:
(apply * (range 1 (inc 5)))
;where inc and range are functions such that:
;  (inc a) returns (+ a 1), and
;  (range a b)  => (a, (+ a 1), ... (- b 1))
;
;We can now define factorial(n):
(def factorial (fn [n] 
                 (apply * (range 1 (inc n)))))
;
;When we 'define' something, we bind a
;symbol to a value. For example:
(def x 5)
;binds the symbol x to the value 5.
;In Clojure, functions are also values.
;
;We could have also written factorial as:
(defn factorial [n] 
  (apply * (range 1 (inc n))))
;where defn is a macro that combines def and fn.
;
;Macros make your code shorter and more
;expressive.
;
;Note that we didn't use loops or any other form
;of control flow in the above implementation..

;;------------------------------------
;;Control Flow, Looping, and Recursion
;;------------------------------------
; ..which doesn't mean that we can't. 
;
;The factorial function can be defined
;recursively as:
;  factorial(n) = if n is {0 or 1} then 1, 
;       otherwise (n * factorial(n-1)).
;
;which, in Clojure, would be:
(defn factorial [n]
  (if (< n 2) 1
    (* n (factorial (dec n)))))
;assuming n is always positive.
;
;Recursive algorithms are simple to read,
;write, and understand, but can be slow 
;and memory-intensive:
;  factorial(5)
;  => 5 * factorial(4)
;  => 5 * (4 * factorial(3))
;  => 5 * (4 * (3 * factorial(2)))
;  => 5 * (4 * (3 * (2 * factorial(1))))
;  => 5 * (4 * (3 * (2 * 1)))
;  => 5 * (4 * (3 * 2))
;  => 5 * (4 * 6)
;  => 5 * 24
;  => 5!
;
;Clojure provides the recur-form to make
;recursion stackless and fast:
(defn factorial [n]
  (letfn [(fact [x f]
            (if (< x 2) f
              (recur (dec x) (* x f))))]
    (fact n 1)))
;where letfn creates a local function fact
;such that:
;  factorial(5)
;  => fact(5, 1)
;  => fact(4, 5)
;  => fact(3, 20)
;  => fact(2, 60)
;  => 5!
;
;which is made easier by the loop macro:
(defn factorial [n]
  (loop [x n, f 1]
    (if (< x 2) f
      (recur (dec x) (* x f)))))
;which acts as a dummy function with
;default parameters.
;
;Did you notice we haven't even created 
;a variable yet?

;;-------------------
;;Variables and State
;;-------------------
;which is not to say we can't.
;
;Atoms are the simplest form of variables:
(def x (atom 5))
;binds x to atom-with-initial-state:5.
;
;We can change the state of an atom:
(swap! x inc)
;state-of-x becomes the value 6.
;
(swap! x * 2)
;changes state-of-x to 12.
;
;state-of-x can be accessed by using either 
;deref or the @ reader-macro:
@x ;=> (deref x)
;returns 12.
;
;The most important thing to note here is 
;that atoms are thread-safe. Anyone can see the
;current state of an atom, but only a single
;thread can modify it at a time.
;
;How would an imperative factorial look in
;Clojure? Glad you asked:
(defn factorial [n]
  (let [f (atom 1)]
    (doseq [i (range 1 (inc n))]
      (swap! f * i))
    @f))
;where let creates local-binding f, and doseq
;iterates over the given sequence with i.
;
;(more to come later)