Thursday, April 16, 2015

Clojure Tutorial 1

My First Clojure script

After some immersion in FRP concepts in Javascript I decided to take the leap and start learning Clojure the popular functional programming language that runs on the Java Virtual Machine (JVM). There is also a great compiler for it to Javascript and many are starting to use Clojurescript to write declarative web-apps.

Here I am going to introduce you to Clojure by means of an example that we can run from the command line.


The problem

For this simple example I am going to implement a script to test an integer passed in from the command line, to see if it is a perfect number or not. A perfect number is a composite integer whose factors, when summed, are equal to the integer itself.

Installation

First we need to install the Clojure automation library leiningen, which I thoroughly recommend for using with all your Clojure projects.

Install Leiningen (copied from leiningen website)

  • Download the lein script (or on Windows lein.bat)
  • Place it on your $PATH where your shell can find it (eg. ~/bin)
  • Set it to be executable (chmod a+x ~/bin/lein)
  • Run it (lein) and it will download the self-install package

now we must install lein-exec to run our script from the command-line

 wget https://raw.github.com/kumarshantanu/lein-exec/master/lein-exec  
 wget https://raw.github.com/kumarshantanu/lein-exec/master/lein-exec-p  
 wget https://raw.github.com/kumarshantanu/lein-exec/master/project.clj  
 chmod a+x lein-exec lein-exec-p project.clj  
 mv lein-exec lein-exec-p ~/bin  # assuming ~/bin is in PATH  

The script

Let’s build this up in parts so it’s easy to understand.

Receiving arguments

#!/bin/bash lein-exec

(let [x (read-string (last *command-line-args*))]
        (println x))

The first line in the file tells bash to use lein-exec to run the script.
The next line reads in the *command-line-args* as a list, takes the last value in the list (our passed argument), converts it to an integer, binds it to the symbol x and prints it out to the command line.

  • Save the file: clj_tutorial.clj
  • Give it permissions: chmod a+x clj_tutorial.clj
  • Run it: ./clj_tutorial.clj 28

it should print out 28 on the command line.

Finding Factors

instead of testing every integer between 1 and the composite integer we’re testing, we can optimise the algorithm to just test all integers up to the square root of the composite integer. We can find all the remaining factors using the calcalation integer/factor

Create a range

So let’s write a function to create a list of all integers up to and including the square root of a number.

(defn getRange [x]
    (range 1 (+ x 1)))

(getRange (Math/sqrt x))

Test for factors

To test if an integer is a factor we use the modulo function, which is part of Clojure.core.

(defn isFactor [x1 x]
    (= 0 (mod x x1)))

where x is the number we’re testing and c is the composite integer.

Find all factors up to sqrt

Let’s put this together to find the factors of the integer up to the square root. We will use the list of integers we created and filter them based on the factor test.

(defn getSubFactors [x]
    (filter #(isFactor % x) (getRange (Math/sqrt x))))

Find all the factors

We now need to find the higher factors as previously explained and create a new list that contains all of the factors.

(defn getFactors [x]
    (let [factors (getSubFactors x)]
        (concat factors (getInvFactors factors x))))

Notice how we use let to bind the expression (getSubFactors x) to the symbol factors

Sum the factors

Functional programming makes a mockery out of how we would normally do a summation in an imperative programming language. In Clojure, this is how we sum the whole collection of factors

(defn sum [x]
    (reduce + x))

Reduce is taking each value of the collection x and applying the 1st argument (+) between the previous result and the current value … this does our summation for us.

Testing for perfect

Now we just have to put these methods together to see if the sum of the factors equals the original composite. In our case the composite itself appears in the list of factors, so we simply test for twice the composite value like this

(defn classify [x]
    (if (= (* 2 x) (sum (getFactors x)))
        (str x " perfect")
        (str x " not perfect")))

Final script

So here is our final script, which should tell us whether or not an integer is perfect. Test it out with the following perfect numbers 6, 28, 496, 8128

#!/bin/bash lein-exec

(defn isFactor [x1 x]
    (= 0 (mod x x1)))

(defn getRange [x]
    (range 1 (+ x 1)))

(defn getSubFactors [x]
    (filter #(isFactor % x) (getRange (Math/sqrt x))))

(defn getInvFactors [x1 x]
    (map #(/ x %) x1))

(defn getFactors [x]
    (let [factors (getSubFactors x)]
        (concat factors (getInvFactors factors x))))

(defn sum [x]
    (reduce + x))

(defn classify [x]
    (if (= (* 2 x) (sum (getFactors x)))
        (str x " perfect")
        (str x " not perfect")))

(let [x (read-string (last *command-line-args*))]
        (println (classify x)))

No comments: