Greatest Common Divisor

The code that works out the greatest common divisor looks like this:

(fn [x y]
  (cond
    (> x y) (recur (- x y) y)
    (< x y) (recur (x (- y x))
    :else x))

Within a cond construction you don't have to put the pair of forms for a condition and a corresponding action in a list of their own like in Scheme, which saves some typing, so long as you don't lose count. The :else in there is not anything special, it's just convenient in that as a symbol it evaluates to true in a boolean context. And we note the use of the recur function without a loop: in this case control loops back to the start of the enclosing function definition, thereby saving a bit more typing.

Map Construction

Today we want to write a line or two of code that will take a vector of keys and a vector of values and construct a map to link them.  Without using the built-in functions to do this, of course.

Well, the function (assoc m k v) takes a map m and returns the (possibly) large map created by adding the key-value combination of k and v.  So, we can loop through our vectors adding successive elements by pairs to a starting map, which we can initialise as the empty map, denoted {}.

As we do not know that the two vectors are the same length we check both of them and proceed only as long as they both have elements.

So our code looks like this:

(fn [ks vs]
  (loop [m {}, ks ks, vs vs]
    (if (and (seq ks) (seq vs))
      (recur (assoc m (first ks) (first vs)) (rest ks) (rest vs))
      m)))

At the start of the loop the map m that we are building is initialised to {}.  The two identifiers ks and vs represent the vectors of keys and values inside the loop and they are initialised to the values that are passed to the function.  When we recur these work their way through those initial values, to (rest ks) (rest (rest ks)) etc.

A Map Function

A map contains pairs, where the first element is the key and the second element is the attached value: you can set one up with curly brackets, for example:

user=> (def partner {:laurel :hardy, :hardy :laurel, :chaplin nil})
#'user/partner

Now you can look up, say, Laurel's partner:

user=> (get partner :laurel)
:hardy

In our map, Chaplin does not have a partner, so you get this:

user=> (get partner :chaplin)
nil

Of course - we made the value nil when we created the map.  However, if we look up someone who is not in the map, we also get nil:

user=> (get partner :abbott)
nil

The problem (A nil key) today is to write the code that will check for the case where the key really is in the map but the value is nil - - as opposed to the case where the key is not in the map.

We need the function contains?, which asks whether a key is in a map:

user=> (contains? partner :abbott)
false
user=> (contains? partner :chaplin)
true

And we also need the useful fact that nil equals nil.  Therefore the code we want looks like this:

(fn [k m]
  (and
    (contains? m k)
    (= (get m k) nil)))

Re-implement map

This brings us to the question of how we would implement the function map itself.

This is a basic building block that takes a function and a list and returns a list created by applying the given function to each of the elements of the given list. To map f onto a sequence, apply f to the first element and join the result onto whatever you get my mapping f onto the rest of the sequence.  So the obvious implementation looks like this:-

(defn mymap [f x]
  (if (seq x)
    (cons (f (first x)) (mymap f (rest x)))
    '()))

For example, increment a list of numbers:

user=> (mymap inc '(1 2 3 4))
(2 3 4 5)

However, the built-in function map is lazy. That is to say, I can apply it to an unlimited list provided I don't try to take the whole result. For example, recall that the function range without any parameters returns a lazy sequence of integers starting from 0 and going on forever:

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

I can still use this as a parameter in map:

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

But if I do this with my reimplementation we get this:

user=> (take 10 (mymap inc (range)))
StackOverflowError clojure.lang.ChunkedCons.first (ChunkedCons.java:37)

Because the recursion in the function mymap starts work on its input list whether it needs it or not and just keeps going. To avoid this we want to write a lazy version of the map. In Clojure this is easier to do than to understand. I'm guided here by Fogus & Hauser, p 166. We add the macro lazy-seq to our map definition:

(defn mymap2 [f x]
  (lazy-seq
    (if (seq x)
      (cons (f (first x)) (mymap2 f (rest x)))
      '())))

Now this works for limited sequences:

user=> (take 3 (mymap2 inc '(1 2 3 4 5 6)))
(2 3 4)

But it also works for infinite ones:

user=> (take 3 (mymap2 inc (range)))
(1 2 3)

hmm. Pretty neat.

For the purposes of the 4Clojure exercise  we need to code this as an anonymous function that has an internally visible name so that it can call itself - you can add a name into the function definition form that will do this, as so:

(fn my-map [f x]
  (lazy-seq
    (if (seq x)
      (cons (f (first x)) (my-map f (rest x)))
      '())))

Here the name my-map is visible just inside the body of the definition.

Value of a binary number

The test today is to write the code that will take a binary number expressed as a string of 0 and 1 characters and convert this to the integer value.

My first thought is to apply the old method where you step by character through the string, starting with an accumulator value initially zero.  Then, for each character, if the character is 1 you double the accumulator and add one, and if the character is 0 you just double your accumulator. When there are no more characters left the accumulator is the result.  So the function is:

(defn convert-binary [s]
  (loop [acc 0, s s]
    (if (seq s)
        (if (= \1 (first s))
            (recur (+ 1 (* 2 acc)) (rest s))
            (recur (* 2 acc) (rest s)))
        val)))

However here we are writing a loop - - surely there is a quick way to bolt together the existing list processing function to do the work?

Well, we want to know the values of the digits, from the lowest upwards.  These of course are the powers of 2, which we can get by iterating adding a number to itself, starting from 1:-

user=>(take 10 (iterate #(+ % %) 1))
(1 2 4 8 16 32 64 128 256 512)

Alongside these we want the digits of the binary string in the order of least to greatest, which is just a matter of using function reverse.

user=>(reverse "1010")
(\0 \1 \0 \1)

Now we can use map to apply a function to these pairs: specifically, if the digit is 0 then return 0, but if the digit is 1 return the power-of-2 value of the digit from the other list.  This gives us a list of numbers corresponding to the absolute values of the digits.  Now we add these up by using reduce +.  Wrap this up as an anonymous function of a binary string b and we get this:-

(fn [b]
  (reduce +
    (map (fn [d v] (if (= \0 d) 0 v))
         (reverse b)
         (iterate #(+ % %) 1))))

No, there is going to be a much simpler way.

The macro ->>

Today's exercise is to make use of the macro ->>.

Consider the case where we have a list of numbers [2 5 4 1 3 6].  We wish to drop the first two, take the next five, increase each one and then add them all together.  Recall that the way to apply a function to a list of elements, such as to add up a list of numbers, is to user reduce:-

user=> (reduce + [2 5 4 1 3 6])
21

So the whole task looks like this:-

user=> (reduce + (map inc (take 3 (drop 2 [2 5 4 1 3 6]))))
11

The macro ->> lets us rewrite this so that the function calls are one after another instead of one inside another.  So this same calculation can be written:-

user=> (->> [2 5 4 1 3 6] (drop 2) (take 3) (map inc) (reduce +))
11

Half-Truth

And today's exercise is to write a function that takes a variable number of booleans and returns true if some but not all of them are true.

There is a function not-every? that takes a predicate and a list and returns false if all the elements of the list satisfy the predicate.  In this case we want to check the list and return true if some element is true (ie not every element is false) and also not every element is true.  Hang on, is that right?  Whatever - whichever way round it is, we want "not every element X" where X is true and false.

So the function we want is this:-

(fn [xs] (and (not-every? true? xs) (not-every? false? xs)))

List Split-At Function

Today's puzzle from the 4-Clojure site it to write a function that will split a list at a given numbered element - - so for example if you split the list (a b c d e) at 2 you get back the lists (a b) - first 2 elements - and the list (c d e) - the rest.

user=> (split-at 2 [:a :b :c :d :e])
[(:a :b) (:c :d :e)]

This is the same as the function split-at which is built in.

The simple solution is to observe that the first list you return is what you get by taking n items from the given list, and the second list is what you get by dropping n items from the list.  Take and drop functions are available already.  Putting that together the function we want looks like this:-

(fn [n xs] (list (take n xs) (drop n xs)))

Alternatively, if we want to do this the hard way, we can write a loop.  At the top of the loop we create a left-hand list, initially empty, and a right-hand list, also initially empty.  Then we scan through the source list item by item, counting our number n down as we go.  As long as n is over zero we add each element to the left hand list: when n drops to zero and below we add each item to the right hand list.  When the source list is finished we return the two new lists we just built.  So the function looks like this:-

(defn hard-split-at [n xs]
 (loop [ls [], rs [], n n, xs xs]
  (if (seq xs)
   (if (> n 0)
    (recur (cons (first xs) ls) rs (- n 1) (rest xs))
    (recur ls (cons (first xs) rs) (- n 1) (rest xs)))
   (list ls rs))))