Basic Destructuring

A couple of examples showing destructuring - using the argument list to break up a composite value passed to a function.  The same principle applies within a let statement so it is easy to see how it works.

The function range produces a list of values from a start to an (exclusive) end number with a specified step:

user=> (range 1 10 3)
(1 4 7)


You can omit the step and it will step by 1:

user=> (range 1 10)
(1 2 3 4 5 6 7 8 9)


You can supply just the end and it will start from 0:

user=> (range 10)
(0 1 2 3 4 5 6 7 8 9)


Call it on its own and it will start at 0 and go on as long as you take numbers out:

user=> (take 20 (range))
(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19)


So, if we pass (range) as a parameter to a let statement, we can deconstruct the first few elements of the list of numbers by using a vector of parameter identifiers like this:

user=> (let [[a b c d e f g] (range)] [c e])
[2 4]


So in the body of the (let), a=0, b=1, c=2, d=3, e=4, f=5, g=6.

And so [c e] returns [2 4]

The additional character & in the parameter deconstruction sets the following identifier to a vector of the remaining parameters that have not yet been assigned.

And the keyword :as indicates that the next identifier will take the value of the whole list.  Therefore:

user=> (let [[a b & c :as d] [1 2 3 4 5]] [a b c d])
[1 2 (3 4 5) [1 2 3 4 5]]


What happens here?  From the input values [1 2 3 4 5], a takes the first value 1, b takes the next value 2, and c takes the remaining values and is set to [3 4 5].  Then d is set to the value of the whole input list, that is [1 2 3 4 5].

Compare this with the case where we do not deconstruct the input - we could set d to be the whole of the input list like so:

user=> (let [d [1 2 3 4 5]] d)
[1 2 3 4 5]


Simple Simple Recursion

The next question asks what the following function will return:

((fn foo [x] (when (> x 0) (conj (foo (dec x)) x))) 5)

I hadn't spotted until now that an anonymous function definition can give the function a name, that is to say a name that is visible inside the definition, so you can easily write recursive lambdas.

Anyway clearly this is going to loop down from 5 to 1, building up a list as it goes - so the answer is

(1 2 3 4 5)

Wrong.  This is what happens:

user=> ((fn foo [x] (when (> x 0) (conj (foo (dec x)) x))) 5)
(5 4 3 2 1)

Ha. Maybe it would be clearer (to me at any rate) if I did this with cons instead of conj:

user=> ((fn foo [x] (when (> x 0) (cons x (foo (dec x))))) 5)
(5 4 3 2 1)

The alternative way with cons instead of conj: the x and the call to foo go round the other way. But for lists, conj and cons do the same thing - they add the new element to the start of the list:

user=> (cons 1 '(2))
(1 2)
user=> (conj '(2) 1)
(1 2)

It's with vectors that conj goes the other way:

user=> (conj [2] 1)
[2 1]

when is like if except there is no else part - when the test returns false the when clause returns nil.
You can conveniently cons onto nil to start a list as you would cons onto the empty list:

user=> (cons :a nil)
(:a)
user=> (cons :a '())
(:a)
user=> (cons :a ())
(:a)

Even though nil and () are not the same.

OK, so in this function what happens is the recursive calls burrow their way down from 5 to zero, get a nil when they are down there, and then pop their way back out consing the numbers 1, 2, 3, 4, 5 onto the return list as they go -

(foo 5)
(cons 5 (foo 4))
(cons 5 (cons 4 (foo 3)))
(cons 5 (cons 4 (cons 3 (foo 2))))
(cons 5 (cons 4 (cons 3 (cons 2 (foo 1)))))
(cons 5 (cons 4 (cons 3 (cons 2 (cons 1 (foo 0))))))
(cons 5 (cons 4 (cons 3 (cons 2 (cons 1 nil)))))
(cons 5 (cons 4 (cons 3 (cons 2 '(1))))
(cons 5 (cons 4 (cons 3 '(2 1)))
(cons 5 (cons 4 '(3 2 1)))
(cons 5 '(4 3 2 1))
'(5 4 3 2 1)

Right.  Got it.

Interleave Two Sequences

Similarly to interleave two sequences, without of course using the interleave function.

So for example [1 2 3] [:a :b :c] => [1 :a 2 :b 3 :c]

(fn [sq1] [sq2]
  (loop [src1 sq1, src2 sq2, dest []]
    (if (and (seq src1) (seq src2))
      (recur
        (rest src1)
        (rest src2)
        (conj dest (first src1) (first src2)))
       dest)))


Transforming Sequences

So with those points in mind here are two examples from 4Clojure.

To pack a sequence - that is to take all runs of one or more equal elements and put them inside their own sub-sequences. At each turn round the loop get the next element and then use take-while to gather equal ones into a sub-list and use drop-while to skip over the ones waiting to be processed, like this:

(defn pack-sequence [sq]
  (loop [src sq, dest []]
    (if (seq src)
      (let [x (first src)]
        (recur
          (drop-while #(= x %) src)
          (conj dest (take-while #(= x %) src))))
      dest)))


So for example (pack-sequence '(1 1 2 2 2 3) => '((1 1) (2 2 2) (3))

And similarly to replicate a sequence, meaning to duplicate each element a nominated number of times: use repeat to do the duplication and concat to add the elements to the growing destination sequence:

(defn replicate-sequence [sq n]
  (loop [src sq, dest []]
    (if (seq src)
      (recur
        (rest src)
        (concat dest (repeat n (first src))))
    dest)))


So for example (replicate-sequence '(1 2 3) 2) => '(1 1 2 2 3 3)

Doing Sequences

So I have invested in The Joy Of Clojure by Fogus & Houser. I just felt like buying a book. Well, with a few of their tips I can update my scheme for transforming sequences. One observation is that "quoting the empty list isn't idiomatic Clojure" (p.34) - so you don't have to write '() because () will do. Another observation is that the idiomatic way to test whether a sequence is empty is to use (seq s), which returns nil if (empty? s), and nil evaluates to boolean false. On p.87 they point out that you can remove that call to reverse on closing a sequence transformation by starting with a vector and using conj instead of cons. So instead of:

(defn copy-sequence-1 [sq]
  (loop [src sq, dest ()]
    (if (seq src)
      (recur
        (rest src)
        (cons (first src) dest))
      (reverse dest))))


You can do this:

(defn copy-sequence-2 [sq]
  (loop [src sq, dest []]
    (if (seq src)
      (recur
        (rest src)
        (conj dest (first src)))
      dest)))


You get a vector back but that's not a problem. In fact we read "in idiomatic Clojure code lists are used almost exclusively to represent code forms" (p.90) - for data rather than code "lists rarely offer any value over vectors".

Removing Duplicates

OK the next task is to remove successive duplicates from a sequence.  There is a Clojure function distinct that nearly does this, but it removes all duplicates, not just successive ones:-

user=> (distinct "Mississippi")
(\M \i \s \p)


My first thought is that I can build this from other existing functions.  First, partition the sequence into pairs of elements, that is to say elements 1 and 2, then elements 2 and 3, then elements 3 and 4 etc.:

user=> (partition 2 1 "Mississippi")
((\M \i) (\i \s) (\s \s) (\s \i) (\i \s) (\s \s) (\s \i) (\i \p) (\p \p) (\p \i))


Now filter out the ones where the elements are the same - ie (first %) is not equal to (second %) - because these are the ones where there is a duplicated element:

user=> (filter #(not (= (first %) (second %))) *1)
((\M \i) (\i \s) (\s \i) (\i \s) (\s \i) (\i \p) (\p \i))


(In the Clojure REPL, *1 returns the result of the previous evaluation)

And now put the remaining pairs back into a sequence by getting the first element of each pair with a map:

user=> (map first *1)
(\M \i \s \i \s \i \p)


Nope - of course this misses the final element of the original list, which was never the first element of one of the pairs.

Incidentally we can turn this sequence back into its original string form as follows:

user=> (apply str *1)
"Misisip"


Anyway, perhaps this will require a purpose built function.  Here is the function that eliminates successive duplicates:

(defn deduplicate [sq]
  (if (empty? sq)
  '()
  (let [x (first sq)
        xs (rest sq)]
    (cons x (deduplicate (drop-while #(= x %) xs))))))


This is a basic pattern to transfer one sequence to another via a recursive function: the part that does the work is the drop-while which removes any elements from the rest of the list that match the element being processed.

To drop this into an existing line of code you would wrap the definition in a (do....) construction and let the value you've just defined be returned as the value of the expression.

However, the rules on 4Clojure say that you can't define any new functions.  Therefore it has to be an anonymous function.  How to write an anonymous recursive function? Hmm.  Here I'm going to use the loop/recur construction, so the function is iterative rather than recursive.  It contains a GOTO rather than a CALL to do the loop.  I pass two parameters, one the source sequence that the elements are coming from and the other a destination sequence which is where they will be accumulated.  Yes anyway it looks like this:

(fn [sq]
  (loop [source sq destination '()]
    (if (empty? source)
        (reverse destination)
        (let [x (first source]
              xs (rest source)]
          (recur
            (drop-while #(= x %) xs)
            (cons head destination))))))


Using a recur you build the destination list the wrong way round so I return the reverse thereof.

Home-made flatten function

OK, the recursive function that flattens:

(defn my-flatten [sq]
  (if (empty? sq)
  '()
  (let [head (first sq)
        tail (rest sq)]
       (if (sequential? head)
          (concat (my-flatten head) (my-flatten tail))
          (cons head (my-flatten tail))))))
So now we have:

user=> (my-flatten '(1 2 3 4 (5 6 ( 7 8 ) 9 10 ) (11 12) 5 6))
(1 2 3 4 5 6 7 8 9 10 11 12 5 6)

Looks about right. So, you transfer a list to another list but if the next element is a list then you flatten this to get the elements out and then concatentate on to the processed version of the rest (you don't cons because this would put the elements back in a list).