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))))

Click Counter

The next example comes also from the Swing Tutorial.  Here we have a button and a label.  The button click adds one to a counter, and the label shows the number on the counter, so you can see how often you have clicked the button.

This is the code:-

(ns clojurecorner
  (:import
      (javax.swing JButton JPanel JFrame JLabel SwingUtilities)
      (java.awt.event ActionListener)
      (java.awt GridLayout)))

(def click-counter (atom 0))

(defn init-gui []
  (. SwingUtilities invokeLater
    (proxy [Runnable] []
      (run []
        (let
          [frame (JFrame. "Swing application")
          button (JButton. "I'm a Swing button!")
          label (JLabel. "Number of click")]
          (.addActionListener button
             (proxy [ActionListener] []
               (actionPerformed [e]
                 (.setText label
                   (str "Clicks: " (swap! click-counter inc))))))
          (doto frame
            (.setDefaultCloseOperation JFrame/EXIT_ON_CLOSE)
            (.setLayout (GridLayout. 0 1))
            (.add button)
            (.add label)
            (.setSize 300 200)
            (.setVisible true)))))))

(JFrame/setDefaultLookAndFeelDecorated true)
(init-gui)

The line (def click-counter (atom 0)) creates an atom - a repository for our click counter - sets the initial value to zero, and gives it the name click-counter.

The line (swap! click-counter inc)) updates the value of the counter atom with the result of applying the function inc to the current value, and it returns the new value - a thread-friendly way to maintain the counter.

The code that handles the click event is wired up to the button via another proxy implementing an interface that supports a single method, like the code that creates the gui - in this case a proxy implementing ActionListener by providing a method actionPerformed.

Stuart Sierra on Digital Digressions has pointed out that this pattern with a single abstract method is going to be common enough to warrant a macro.  Yes I'll try that next week.  Anyway, this is how the application looks:

Hello to GUI

The next example shows the minimum possible graphical user interface application. It consists just of a window with the words “Hello World” written in it. This is based on the first example in the Java Swing Tutorial. Here is the Clojure code:

(ns clojurecorner
  (:import (javax.swing JFrame JLabel SwingUtilities)))

(defn create-and-show-gui []
  (. SwingUtilities invokeLater
    (proxy [Runnable] []
      (run []
        (JFrame/setDefaultLookAndFeelDecorated true)
        (let [frame (JFrame. "Hello World from Swing")
              label (JLabel. "Hello World")]
          (.setDefaultCloseOperation frame JFrame/EXIT_ON_CLOSE)
          (.add (.getContentPane frame) label)
          (.pack frame)
          (.setVisible frame true))))))

(create-and-show-gui)

There are various new things happening here. Well, new to me.  First, we have imported some items from the Swing library: JFrame is the object that produces the window on the desktop, and JLabel will support the label that we will put in the frame. SwingUtilities provides essential code to run the application.

The example consists mostly of the call to the function create-and-show-gui. Now, to make this work properly we want this code to be executed in the event dispatch thread, not in our forground thread. We achieve this by passing the code to the function invokeLater in the Swing object SwingUtilities. This function requires an object that implements the interface Runnable, which essentially means it has to provide a function run(). To pass our code to the Java routines we bundle it up into a proxy: the Clojure function proxy takes, first, the class or interface to be represented (here it's Runnable), then any parameters required by a superclass (none here), and then the function or functions to be implemented – in this case the function run.

So the code in run is executed via the call to SwingUtilities.invokeLater() - this means that our main code calls this and then proceeds, allowing Swing to run the code to create the window in its own time in its own thread.

Within the function run we start by switching on the default look and feel for the GUI – that is to say the default Swing appearance. Without this the interface will get your native GUI appearance. It will still work like that, of course, it's just a matter of how you want it to look.

Next we create a frame object from the class JFrame and a label object from the class JLabel.

The next line sets the close operation to halt the program – this means that when you click the close box in the frame the application will actually close as you would expect, not just sit there.

The call to function .add inserts the label into the content area of the label, so the text will appear in the window.

The call to .pack makes the components shuffle into position and then the call to setVisible allows the window to appear on the screen.

When it appears it is in its tiniest area, but you can drag it around and open it up to read what the label says.  So it does the minimum that a GUI window needs to do.  You have to start somewhere.