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.

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

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)