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)