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.

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.

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?
 

A Type Error

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

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)
 

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)

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)