Friday 14 December 2012

December is Here

No, that last code still looks a mess.  But it is written against the requirement for a single block of code that can be pasted into an on-line exercise.  December is here and as far as Clojure is concerned I'm still tinkering with basic exercises.  How do they manage, those folks who undertake to learn a new language every year?  They use the new language to solve their real problems.  Hmm.

Wednesday 14 November 2012

Just the Squares Continued

Yes, putting that function together in a different way:-

(def just-squares
  (fn [s]
    (let [split-string (fn [s] (clojure.string/split s #",")),
      join-strings (fn [ss] (clojure.string/join "," ss)),
      square? (fn [n] (let [root (int (. Math sqrt n))] (= (* root root) n))),
      filter-squares (fn [ns] (filter square? ns)),
      strs->ints (fn [ss] (map #(. Integer parseInt %) ss)),
      ints->strs (fn [ns] (map str ns))]
      (-> s split-string strs->ints filter-squares ints->strs join-strings))))


Tuesday 13 November 2012

Just the Squares

Today's exercise is to take a string that contains numbers separated by commas, like this:

"3,4,5,6,7,8,9"

and return the same except containing only the numbers that are perfect squares, which in this case would be

"4,9"

So the first step is to break up that string into the individual numbers.  In the Clojure String library we get the split function, which takes your string and a regular expression that determines what part of the string is to be used to split.  We're using just about the simplest possible option, just chopping through the commas.  A function to do this would look so:

(defn split-string [s]
  (clojure.string/split s #","))


This gives us a sequence of the separated strings:-

user=> (split-string "4,5,45,6,7,67")
["4" "5" "45" "6" "7" "67"]


When we want to join these back again to restore the single string we have split's partner join, so:-

(defn join-string [ss]
  (clojure.string/join "," ss))


We just specify the string "," to be added between the strings in our sequence.

user=> (join-string ["4" "5" "45" "6" "7" "67"])
"4,5,45,6,7,67"


Now we will want to get the integer values of these strings.  So we dip into the Java class Integer and bring back the method parseInt.  I love it when you can step between languages and they play nicely together.  In the system I use professionally I can step from C to assembler and back again. It's similar in that Clojure has Java hiding inside and C has assembler hiding inside. Anyway to change a string to an integer I can summon the Integer class and call the parseInt method on it, like this:-

user=> (. Integer parseInt "123")
123


That's a macro but it can become a function quite easily:-

user=> (#(. Integer parseInt %) "123")
123


And we will want to convert these integers back into strings: the Clojure function str will do this:-

user=> (str 3)
"3"


We will want a filter function that will decide whether a number is a square.  For this let's dip into Java again and get the square root method from the Math class:-

user=> (. Math sqrt 2.0)
1.4142135623730951


So if I take the integer part of the square root (the Clojure function int will give this) and square this and compare with the original number that indicates whether it is was a square number. Along these lines:-

(defn is-square [n]
  (let [root (int (. Math sqrt n))]
    (= (* root root) n)))


user=> (is-square 100)
true
user=> (is-square 101)
false
user=> (is-square 99)
false


OK so putting the parts together.  The first version of my function just-squares will open up the string into the individual numbers and then put them together again:-

(def just-squares
  (fn [s]
    (join-string (split-string s))))


user=> (def s "4,5,6,7,8,9")
#'user/s
user=> (just-squares s)
"4,5,6,7,8,9"


So far so good.  Now convert them to integers and back again.

(def just-squares
  (fn [s]
    (join-string
      (map str
        (map #(. Integer parseInt %) (split-string s))))))


user=> (just-squares s)
"4,5,6,7,8,9"


Still works.  Now add that filter to allow only the square ones:-

(def just-squares
  (fn [s]
    (join-string
      (map str
        (filter (fn [n] (let [root (int (. Math sqrt n))](= (* root root) n)))
          (map #(. Integer parseInt %) (split-string s)))))))


user=> (just-squares s)
"4,9"


Ok so this works.  Now to make this code complete in itself I should fill in the definitions of those functions split-string and join-string, so we get this:-

(def just-squares
  (fn [s]
    (#(clojure.string/join "," %)
      (map str
        (filter (fn [n] (let [root (int (. Math sqrt n))](= (* root root) n)))
          (map #(. Integer parseInt %) (clojure.string/split s #",")))))))


Hmm.  Well, that works on the 4Clojure page but I don't like it.  Maybe there's scope to use the -> macro to link the sections together instead of nesting them. Or use more lets to give the sections some names.

Also a more idiomatic name for is-square would have been square?.

Wednesday 7 November 2012

Reverse Interleave

Today's example is a reverse interleave - - that is, instead of taking two or more sequences and blending them together, we take one sequence and split it down into two or more by adding elements from the original sequence to the new sequences in rotation.

For example we want the function f that does this:-

(f '(1 2 3 4 5 6) 2) => ((1 3 5) (2 4 6)) ; split into two
(f '(1 2 3 4 5 6) 3) => ((1 4) (2 5) (3 6)) ; split into three

OK, so I expect I will want code to get every nth element from a sequence - every 2nd, every 3rd one etc. The built-in function partition-all splits a sequence into sequences of a nominated length: so all I want from this is the first element of every sub-sequence.  I map first onto the sequence of sequences returned by partition-all:-

user=> (def t '(1 2 3 4 5 6))
#'user/t
user=> t
(1 2 3 4 5 6)
user=> (partition-all 2 t)
((1 2) (3 4) (5 6))
user=> (partition-all 3 t)
((1 2 3) (4 5 6))
user=> (map first (partition-all 2 t))
(1 3 5)
user=> (map first (partition-all 3 t))
(1 4)


Then moving on I will want to get every nth element but not starting at the beginning, starting at some i-th element in.  So I have to drop some elements before the rest of the function gets it - something like this:-

defn every-nth-from-i
  "return every nth item from sequence s starting from element i (counting from zero)"
  [n s i]
  (map first (partition-all n (drop i s))))


user=> (every-nth-from-i 3 t 0)
(1 4)
user=> (every-nth-from-i 3 t 1)
(2 5)
user=> (every-nth-from-i 3 t 2)
(3 6)


Now the result I want is a sequence of all the sequences generated by this code, for each value of i up to the length of the sub-sequences I want to generate. Well, one less.  That's ok, given n I want to map the numbers in (range n) to the every-nth code.

(def reverse-interleave
  (fn [n s]
    (map
      (fn [i] (map first (partition-all n (drop i s))))
      (range 0 n))))


I don't need to explicitly pass n and s to the internal function because it executes in the environment where they are already available.

Does this work?

user=> (reverse-interleave 2 t)
((1 3 5) (2 4 6))
user=> (reverse-interleave 3 t)
((1 4) (2 5) (3 6))


Actually that turned out simpler than I expected.

Friday 2 November 2012

Rotate Sequence

Today, for exercise No. 44 Rotate Sequence we write code to rotate a sequence in either direction - determined by the sign of the first parameter.

To rotate the first element of a list to the end we make a list of the first element and concatenate the rest of the list onto it, like this:

#(concat (rest %) (list (first %)))

For example:

user=> (#(concat (rest %) (list (first %))) '(1 2 3 4 5))
(2 3 4 5 1)


To rotate the other way we could use last to get the end element and butlast to get the others and then swap these around in the same way:

user=> (#(concat (list (last %)) (butlast %)) '(1 2 3 4 5))
(5 1 2 3 4)


This just moves one element - to move more I can make the function recursive.  As the function is recursive anyway I can implement the reverse rotation for negative counts by reversing the original list, rotating it forwards, then reversing the result.  The call to the negative version only happens once - the forward rotation call that does the work is still tail recursive.

You can make an anonymous function recursive by adding a label (in this case this) between the keyword fn and the parameter list. The base case is when the number of rotations left to do is zero: then of course we just return the list. On that basis then we get this:-

(def my-rotate
  (fn this [n xs]
    (if (= 0 n)
        xs
        (if (> n 0) ; n is +ve
          (this (dec n) (concat (rest xs) (list (first xs))))
          (reverse (this (- 0 n) (reverse xs)))))))


How does this look?

user=> (my-rotate 2 [1 2 3 4 5])
(3 4 5 1 2)
user=> (my-rotate -2 [1 2 3 4 5])
(4 5 1 2 3)
user=> (my-rotate 6 [1 2 3 4 5])
(2 3 4 5 1)
user=> (my-rotate 1 '(:a :b :c))
(:b :c :a)
user=> (my-rotate -4 '(:a :b :c))
(:c :a :b)


Thursday 1 November 2012

Flipping Out Continued

And to test the flip-out function I needed a function that takes three parameters where the order matters.  So I added this:

(defn drop-take
  "Drop i elements from the sequence s and then take j of what's left"
  [i j s]
  (take j (drop i s)))


Then to test:

user=> (drop-take 10 5 (range))
(10 11 12 13 14)


user=> ((flip-out drop-take) 5 10 (range))
IllegalArgumentException Don't know how to create ISeq from: java.lang.Long  clojure.lang.RT.seqFrom (RT.java:494)


Ha - pay attention - arguments in the reverse order, remember?

user=> ((flip-out drop-take) (range) 5 10)
(10 11 12 13 14)


That's more like it.

I'm puzzled that I had to rebuild the parameter list by writing

([x y & more] (apply f (reverse (cons x (cons y more)))))

I thought this might work:

([x y & more :as s] (apply f (reverse (s)))

But no, more research required...

Wednesday 31 October 2012

Flipping Out

The next exercise is No. 46, Flipping Out: to write a higher-order function that flips the order of the arguments of an input function.  the lesson today is how to define a function when you do not know how many arguments it will be passed when it is called.

So I am writing a function flip-out that takes a function f as argument and returns a new function...

(def flip-out
  (fn [f]...

 
What does is new function supposed to do when I call it?  If there are no arguments, it returns whatever the starting function would have returned:

     ([] (f))
    
No, it doesn't return the function we started with , which would be:

    ([] f)
   
...it calls said function and returns the result:

     ([] (f))
    
If the new function is called with one argument x then call the function with that argument:

      ([x] (f x))
     
If it is called with two arguments x and y then call the function with these arguments but in the other order as per the spec:

      ([x y] (f y x))
     
And finally if there are more than two argument our parameter list looks like this: the first argument x, the second argument y, and then a sequence of the remaining arguments conventionally labelled more:

    [x y & more]
   
So we rebuild the argument list and reverse it:

 (reverse (cons x (cons y more)))

...and apply our original function to the result. There is a higher-order function that does this, coincidentally called apply.  For example:

user=> (+ 1 2 3 4)
10
user=> (apply + '(1 2 3 4)) ; same thing
10


So we use apply thus:

    (apply f (reverse (cons x (cons y more))))
   
So the whole function looks like this:

(def flip-out
  (fn [f]
    (fn
        ([] (f))
        ([x] (f x))
        ([x y] (f y x))
        ([x y & more] (apply f (reverse (cons x (cons y more))))))))


This defines the result as a function for testing.  To stick this into the 4Clojure page we need just the bit inside the definition.

Monday 29 October 2012

Alert

If you unexpectedly find yourself ahead of schedule on a large project, take another good look at the spec.  Maybe you forgot something important early on - -

Wednesday 15 August 2012

Drop every nth item - corrected

A keen eyed Clojurian has spotted that my revised function for dropping every nth item from a sequence has a bug.  It was this function:-

(defn drop-nth [n s]
  (flatten (map drop-last (partition-all n s))))


My mistake was that by using partition-all to break up the original sequence I get a final sub-sequence that will generally have less than n elements.  Therefore when I drop-last I lose one element I wanted to keep.  For example all these sequences should include the final element 13:-

user=> (def s [1 2 3 4 5 6 7 8 9 10 11 12 13])
#'user/s
user=> s
[1 2 3 4 5 6 7 8 9 10 11 12 13]
user=> (drop-nth 3 s)
(1 2 4 5 7 8 10 11)
user=> (drop-nth 4 s)
(1 2 3 5 6 7 9 10 11)
user=> (drop-nth 5 s)
(1 2 3 4 6 7 8 9 11 12)


So really instead of dropping the last element on the assumption that there are n altogether I need to take n-1 elements.  So the function now looks like this:-

(defn drop-nth [n s]
  (flatten (map #(take (- n 1) %) (partition-all n s))))


user=> (drop-nth 3 s)
(1 2 4 5 7 8 10 11 13)
user=> (drop-nth 4 s)
(1 2 3 5 6 7 9 10 11 13)
user=> (drop-nth 5 s)
(1 2 3 4 6 7 8 9 11 12 13)


That's more like it.

Monday 18 June 2012

Anagram Finder

Picking a problem at random today, I find http://www.4clojure.com/problem/77 the objective is to take a list of words and return a set of sets of words where each set of words contains two or more words from the original list that are anagrams of each other.

For example starting from this list

user=> (def s ["meat" "mat" "team" "mate" "eat"])
#'user/s
user=> s
["meat" "mat" "team" "mate" "eat"]


We want to get this:-

#{#{"mate" "meat" "team"}}

Now, strings in Clojure are sequences and therefore they can be sorted.  If two words are anagrams then when you sort them they return the same list of letters.  So the quick test is #(= (sort %1) (sort %2))

user=> (#(= (sort %1) (sort %2)) "meat" "team")
true
user=> (#(= (sort %1) (sort %2)) "meat" "vale")
false


To rearrange our source list we call upon the built-in list function group-by, which gathers together items from a list that return the same value to a given function.  For our purposes this function required is just sort, because we want to group together words with the same letters:-

user=> (group-by sort s)
{(\a \e \m \t) ["meat" "team" "mate"], (\a \m \t) ["mat"], (\a \e \t) ["eat"]}


Well, here we get back a complete map.  We don't need the keys to the map - that is to say the actual list of letters that each word contains - we just want the values, the lists of matching words: the map function vals does this:-

user=> (vals (group-by sort s))
(["meat" "team" "mate"] ["mat"] ["eat"])


But I do not want to see ["mat"] nor ["eat"] in the output because we are asked for sets only where there are two or more anagrams.  So I am going to filter these out, and the required predicate - well, seq will eliminate empty lists, and I can combine this with rest to eliminate lists with only one element - so my predicate is going to be (comp seq rest):-

user=> (filter (comp seq rest) (vals (group-by sort s)))
(["meat" "team" "mate"])


The requirements ask for a set of sets, so I will map the set creator function set into my returned sequence and apply it to the whole list, so:-

user=> (set (map set (filter (comp seq rest) (vals (group-by sort s)))))
#{#{"mate" "meat" "team"}}


So the function than answers the problem is

#(set (map set (filter (comp seq rest) (vals (group-by sort %)))))

Hmm. The disturbing thing about that code is that because it is just a sequence of faceless off-the-shelf built in functions it offers no clue as to what it does. You could be tempted to rewrite to use some local functions with descriptive names - not to change the function but to make the code less Sphinxlike.  Maybe

(defn anagram-set [word-list]
  (let
    [anagram sort,
    two-or-more (comp seq rest)]
    (set (map set (filter two-or-more (vals (group-by anagram word-list)))))))
     

Or something.  I don't know.

Monday 28 May 2012

Drop every nth item revised

A friendly Clojurian has pointed out that I gave up too soon on my first attempt to create a function that drops every nth element from a sequence.

If you start with a sequence:-

user=> (def s (range 1 20))
#'user/s
user=> s
(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19)


You can break this into sections where all except the last one have n elements and the final one has up to n elements depending on how many are left: this is the function partition-all:-

user=> (partition-all 4 s)
((1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 16) (17 18 19))
user=> (partition-all 5 s)
((1 2 3 4 5) (6 7 8 9 10) (11 12 13 14 15) (16 17 18 19))
user=> (partition-all 6 s)
((1 2 3 4 5 6) (7 8 9 10 11 12) (13 14 15 16 17 18) (19))


This is different from function partition, which would silently omit the final elements if there were not enough to make another batch of n.

So now I can take only n-1 elements from each batch, there's a function drop-last which does this:

user=> (map drop-last (partition-all 6 s))
((1 2 3 4 5) (7 8 9 10 11) (13 14 15 16 17) (19))


So the final element from each batch of 6 goes.  Then flatten the batches to make a single sequence:-

user=> (flatten (map drop-last (partition-all 6 s)))
(1 2 3 4 5 7 8 9 10 11 13 14 15 16 17 19)


There we are, each 6th element dropped.  Far more functional than the solution that works through the list.

Therefore the function to drop every nth item from a sequence looks like this:

(defn drop-nth [n s]
  (flatten (map drop-last (partition-all n s))))


Isn't that honey?
 

Wednesday 9 May 2012

A Type Error

Questionmaster:  Name something you might do during a game of football.
Contestant: Pass

Wednesday 2 May 2012

Home grown iterate function

The next exercise is to duplicate the function iterate, which takes a function f and a starting value x and returns a lazy list of x, (f x), (f (f x)), (f (f (f x))) etc. For example:-

 user=> (take 10 (iterate inc 99)) 
(99 100 101 102 103 104 105 106 107 108)

 The un-lazy version would look like this:-

(defn my-iterate-1 [f x]
(cons x (my-iterate-1 f (f x))))


This will not work, or, rather, it works too well and does not know how to stop:-

user=> (take 10 (my-iterate-1 inc 99))
StackOverflowError   clojure.lang.Numbers$LongOps.inc (Numbers.java:510)


What we really want is this:-

(defn my-iterate-2 [f x]
(lazy-seq
(cons x (my-iterate-2 f (f x)))))


user=> (take 10 (my-iterate-2 inc 99))
(99 100 101 102 103 104 105 106 107 108)


To create a recursive anonymous version of the function we write it like this:-

(fn this [f x]
  (lazy-seq
    (cons x (this f (f x)))))

 
Then it can be slotted into the examples on 4Clojure.

The other obvious possible solution is not lazy:-

(defn my-iterate-3 [f x]
(lazy-seq
(conj (my-iterate-3 f (f x)) x)))


user=> (take 10 (my-iterate-3 inc 99))
StackOverflowError   user/my-iterate-3/fn--90 (myiterate.clj:11)

 

Monday 12 March 2012

Sequence Reductions again

OK that function to get the beginning sections of a list is bugging me.

A neater way is with a list comprehension: work my way down the sequence with (drop ...) until the end (no more (seq ...)) and use these numbers to (take...) sections from the start of the list:

(defn heads [s]
  (for [n (range) :while (seq (drop n s))]
    (take (inc n) s)))


So if I go

user=> (def x '(1 2 3 4 5 6 7 8))
#'user/x


Then I get the initial sections of increasing length:

user=> (heads x)
((1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5) (1 2 3 4 5 6) (1 2 3 4 5 6 7) (1 2 3 4 5 6 7 8))


And it's lazy - I can pass (range) as an argument:

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


Now I can make the function that does successively greater reductions like so:

(defn myreduce [f s]
  (map #(reduce f %) (heads s)))


For example:

user=> (reduce + x)
36
user=> (myreduce + x)
(1 3 6 10 15 21 28 36)
user=> (reduce * x)
40320
user=> (myreduce * x)
(1 2 6 24 120 720 5040 40320)

Tuesday 28 February 2012

Sequence Reductions

The next puzzle Sequence Reductions is to write a function that is like reduce, but instead of just returning the final value it returns the intermediate values as well in a list. It needs to be lazy and it should allow either two or three arguments.

OK as a preliminary I want a list of all the initial segments of the list, going up to the complete list.  Define function heads:-

(defn heads [s]
  (for [n (range (count s))]
    (take n s)))


try this:

user=> (def s '(3 1 4 1 5 9))
#'user/s
user=> (heads s)
(() (3) (3 1) (3 1 4) (3 1 4 1) (3 1 4 1 5))


No, not right - I want to start from one element not none.  This should be this:

(defn heads [s]
  (for [n (range (count s))]
    (take (inc n) s)))
user=> (heads s)
((3) (3 1) (3 1 4) (3 1 4 1) (3 1 4 1 5) (3 1 4 1 5 9))


That's the list of initial sections of the input list.

No, hang on.  I want the result to be lazy, but there's (count s) in there - this will have to evaluate its argument so it can't be lazy.

I can take 6 from range...

user=> (take 6 (range))
(0 1 2 3 4 5)


But pass this through the function:

user=> (take 6 (heads (range)))

....never returns because it tries to count an infinite list.

OK, different approach.

I want a function that will retain the whole list.  But also I want to step through the list item by item so I know when to stop.  Try a function inside the function, like this:-

(def s '(1 2 3 4 5 6))
(defn heads [s]
  (map (fn [n x] (take (inc n) s))
       (range)
       s))


This does the job of assembling the sub-sections of the list, like this:

user=> (heads s)
((1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5) (1 2 3 4 5 6))


and it's lazy:

user=> (take 4 (heads (range)))
((0) (0 1) (0 1 2) (0 1 2 3))


OK, now to build a multiple reduce function by applying the real reduce function to all these sub-lists from the list:

(defn myreduce [f s]
  (map #(reduce f %)
         (map (fn [n x] (take (inc n) s))
          (range)
          s)))


So we get this:

user=> s
(1 2 3 4 5 6)
user=> (myreduce + s)
(1 3 6 10 15 21)
user=> (myreduce * s)
(1 2 6 24 120 720)


Looks ok.  Also I want to be able to call it with a starting number followed by the rest of the list as an alternative to just the list.  Open up the function so that the assignment to the identifier is separate from the definition so I can use this separately. In the body of the function definition we can have two definitions, one for the parameter list [f s] and one for the list [f x s] where x is a new element to start.  The body of the function for this list just adds the new element to the list and then calls the two-parameter version via the internal identifier this.

(def myreduce
  (fn this
    ([f s]
      (map #(reduce f %)
           (map (fn [n x] (take (inc n) s))
                (range)
                s)))
    ([f x s]
      (this f (cons x s)))))


So does this work?

user=> (myreduce * 10 s)
(10 10 20 60 240 1200 7200)
user=> (myreduce + 10 s)
(10 11 13 16 20 25 31)
user=> (myreduce + (cons 10 s))
(10 11 13 16 20 25 31)

Monday 27 February 2012

Lazy Evaluation

3 . 1 4 1 5 9
Seek that value, line by line:
Slice your logic, chop it fine.

Must you break the silent spell?
Got your answer? Read it well -
Symbols too have lies to tell.

Which is value? Which is sign?
Spill your secret - I keep mine:
2 6 5 3 5 8 9

Monday 30 January 2012

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.

Wednesday 25 January 2012

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.

Tuesday 24 January 2012

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

Thursday 19 January 2012

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.

Wednesday 18 January 2012

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.

Tuesday 17 January 2012

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

Wednesday 11 January 2012

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

Monday 9 January 2012

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