On The Art of Programming

Foreword

This article is meant to guide the reader through the process of writing a program.

More importantly, it is intended to introduce the non-initiated hackers to the powerful world of functional programming and Lisp.

Introduction to Clojure

. Clojure is a dialect of Lisp, which is a family of programming languages.

. Lisp stands for list processing, and that is the core of the idea - everything is a list.

. Unless specified otherwise, lists are (eventually) evaluated, and are called forms.

. Clojure is built around the idea of immutability of state, which is pretty new and exciting.
. Many things in Clojure are lazy, ie, they are evaluated when and only if they are absolutely needed.

In Lisp, a form looks like this: (form-name x y z ...)
form-name can be one of 3 things: function-name, special-form-name, or macro-name.
The form (+ 1 2) evaluates to 3. + is a function, 1 and 2 are its arguments.


Aim

Our aim is to create a function infer-seq that takes a sequence as input and returns an infinite list created by extrapolating the input sequence using the Method of Differences.

Basically, we are implementing Babbage's Difference Engine in code. Awesome.

Use cases:

    (infer-seq [1 2])    ;=> (1 2 3 4 ...)    
    (infer-seq [10 8])   ;=> (10 8 6 4 ...)   
    (infer-seq [1 4 9])  ;=> (1 4 9 16 25 ...)

Code

Step 1
We first define a function diffs to get the list of differences for a pattern.

Use Case:
    (diffs [1 4 9]) ;=> (3 5)

Implementation:

    (defn diffs [pattern]
         (map - (rest pattern) pattern))

Working:
    (diffs [1 4 9])

  => (map - 
          (rest [1 4 9])
          [1 4 9])

  => (map - 
          [4 9]
          [1 4 9])

  => [(- 4 1) (- 9 4)]

  => [3 5]

Note:
    . As map iterates till the end of the smaller list, the 9 in the second list is simply ignored.

Step 2
We then define get-triangle as per the method of differences.

Use Case:
    (get-triangle [1 4 9]) ;=> ((1 4 9) (3 5) (2))

Implementation:

    (defn get-triangle [pattern]
         (take (count pattern) (iterate diffs pattern)))

Working:
    (get-triangle [1 4 9])

  => (take (count [1 4 9])
           (iterate diffs [1 4 9]))

  => (take 3
           [[1 4 9] [3 5] [2] [] [] [] ...])

  => [[1 4 9] [3 5] [2]]

Note:
     . As Clojure is lazy, the empty lists after [2] would never even exist.

Step 3
Finally, we define infer-seq.

Use Case:
    (infer-seq [1 4 9]) ;=>  (1 4 9 16 25 ...)

Implementation:

    (defn infer-seq [pattern]
         (->> (get-triangle pattern)
              (map last)
              reverse
              (iterate #(reductions + %))
              (map last)
              rest
              (concat pattern)))

Working:
    (infer-seq [1 4 9])

    => (->> (get-triangle [1 4 9])
          ...)
    
    => (->> [[1 4 9] [3 5] [2]]
          ...)

      => (map last [[1 4 9] [3 5] [2]])
      => [9 5 2]

      => (reverse [9 5 2])
      => [2 5 9]

      => (iterate #(reductions + %) [2 5 9])
      => [[2 5 9] [2 7 16] [2 9 25] ...]

      => (map last [[2 5 9] [2 7 16] [2 9 25] ...])
      => [9 16 25 ...]

      => (rest [9 16 25 ...])
      => [16 25 ...]

      => (concat [1 4 9] [16 25 ...])
      => [1 4 9 16 25 ...]

Note:
     . This example will help you understand how the ->> macro works.
     . #( ... ) is a reader-macro for writing anonymous functions in Clojure.
       Its arguments are: % %2 %3 ...
       Example: (map #(+ % 5) [1 2 3]) ;=> (6 7 8)
     . (reductions + [...]) returns the cumulative sums of a sequence.
       Example: (reductions + [1 2 3 4 5]) ;=> (1 3 6 10 15)


Complete Code

(defn diffs [pattern]
     (map - (rest pattern) pattern))

(defn get-triangle [pattern]
     (take (count pattern) (iterate diffs pattern)))

(defn infer-seq [pattern]
     (->> (get-triangle pattern)
          (map last)
          reverse
          (iterate #(reductions + %))
          (map last)
          rest
          (concat pattern)))

Conclusion

I had an awesome time writing this post.
Hope it encourages more people to check Lisp out.

Note

My original implementation was pretty memory intensive.
This version was suggested to me on StackOverflow.

Edit 1: Here's an equivalent in Python.