Missing fns: rotate & rotate-while

[Sean Devlin]

Hey everyone,

I've had to code these guys up a few times:

(defn rotate
"Take a collection and left rotates it n steps. If n is negative,
the
collection is rotated right. Executes in O(n) time."
[n coll]
(let [c (count coll)]
(take c (drop (mod n c) (cycle coll)))))

(defn rotate-while
"Rotates a collection left while (pred item) is true. Will return a
unrotated
sequence if (pred item) is never true. Executes in O(n) time."
[pred coll]
(let [head (drop-while pred coll)]
(take (count coll) (concat head coll))))

Have other people had this problem?

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

[Michał Marczyk]

On 21 April 2010 17:23, Sean Devlin <francoi...@gmail.com> wrote:
> I've had to code these guys up a few times:

Nice functions!

I'd replace "collection" with "sequence" in the docstrings, though.
(And rename the args accordingly.)

You can also rewrite rotate as

(defn rotate [n s]
(lazy-cat (drop n s)
(take n s)))

which has the built-in assumption that n doesn't exceed the length of
s, but won't force more than (inc n) elements of s before producing
the first item of the result. (Additional forcing might happen due to
chunking issues, of course.)

As a final remark, I believe that rotate takes constant time to
execute, followed by O(n) time to produce the first element. This is
petty nitpicking, of course. ;-)

Sincerely,
Michał

[Sean Devlin]

You're right about changing the docstring to read ""sequence"

I think the lazy-cat version looses the ability to rotate in reverse,
which I've come to love from Ruby. Also, I have found use cases where
I want to rotate a period longer than the sequence length.

Thanks for the feedback, though.
Sean

On Apr 21, 11:37 am, Michał Marczyk <michal.marc...@gmail.com> wrote:

[Michał Marczyk]

On 21 April 2010 17:46, Sean Devlin <francoi...@gmail.com> wrote:
> I think the lazy-cat version looses the ability to rotate in reverse,
> which I've come to love from Ruby.  Also, I have found use cases where
> I want to rotate a period longer than the sequence length.

Right. I don't mind rotate being strict, actually, I'm just playing
around and being silly:

(defn rotate [n s]
(if-let [remaining (and (not (neg? n))
(seq (drop n s)))]
(lazy-cat remaining
(take n s))
(let [c (count s)]
(take c (drop (mod n c) (cycle s))))))

Seriously though, I'd vote for your original versions to go into c.c.seq.

[Mark Engelberg]

On Wed, Apr 21, 2010 at 8:46 AM, Sean Devlin <francoi...@gmail.com> wrote:
> You're right about changing the docstring to read ""sequence"
>
> I think the lazy-cat version looses the ability to rotate in reverse,
> which I've come to love from Ruby.  Also, I have found use cases where
> I want to rotate a period longer than the sequence length.
>
> Thanks for the feedback, though.
> Sean

The use of concatenation as opposed to cycle does not affect the
ability to rotate in reverse or more than the sequence length provided
you use mod to get the number in range first:

(defn rotate [n s]
(let [shift (mod n (count s))]
(concat (drop shift s)
(take shift s))))

[could use lazy-cat instead of concat, but I doubt it's worthwhile here]

[Sean Devlin]

Hmmm... good point. Now that I think about it, cycle is an artifact
of an early implementation.

On Apr 21, 1:01 pm, Mark Engelberg <mark.engelb...@gmail.com> wrote:

[Michał Marczyk]

One could also do

(defn rotate [n s]
(let [[front back] (split-at (mod n (count s)) s)]
(concat back front)))

I was hoping for a moment to avoid calculating (count s) up front, but
that definitely does interfere with negative / large shifts, so never
mind that.

Sincerely,
Michał

[Sean Devlin]

I like that version :)

[Michał Marczyk]

On 21 April 2010 19:35, Sean Devlin <francoi...@gmail.com> wrote:
> I like that version :)

:-)

In this case, rotate-while could be rewritten like so:

(defn rotate-with [pred s]
(let [[front back] (split-with pred s)]
(concat back front)))

And to round it off with ridiculous overengineering ;-) --

(defn rotate* [n-or-pred s]
(let [with? (ifn? n-or-pred)
[front back] ((if with?
split-with
split-at)
(if with?
n-or-pred
(mod n-or-pred (count s)))
s)]
(concat back front)))

[Sean Devlin]

If you're gonna over engineer use a protocol :-p

On Apr 21, 1:43 pm, Michał Marczyk <michal.marc...@gmail.com> wrote:

[Mark Engelberg]

In some languages, split-at is more performant than doing take and
drop separately. But in Clojure, split-at is simply defined as:
(defn split-at
"Returns a vector of [(take n coll) (drop n coll)]"
[n coll]
[(take n coll) (drop n coll)])

So by using split-at, you gain nothing other than the additional
overhead of constructing a vector and then turning around and
destructuring it.

On Wed, Apr 21, 2010 at 10:11 AM, Michał Marczyk
<michal....@gmail.com> wrote:
> One could also do
>
> (defn rotate [n s]
>  (let [[front back] (split-at (mod n (count s)) s)]
>    (concat back front)))
>

[Sean Devlin]

Hmmm... we could talk about what's faster or measure it. Time to eat
my own damn dog food, I guess :)

Traveling now, I'll run the experiments in a few days when I get back
to my normal setup.

Sean

On Apr 21, 2:09 pm, Mark Engelberg <mark.engelb...@gmail.com> wrote:
> In some languages, split-at is more performant than doing take and
> drop separately.  But in Clojure, split-at is simply defined as:
> (defn split-at
>   "Returns a vector of [(take n coll) (drop n coll)]"
>   [n coll]
>     [(take n coll) (drop n coll)])
>
> So by using split-at, you gain nothing other than the additional
> overhead of constructing a vector and then turning around and
> destructuring it.
>
> On Wed, Apr 21, 2010 at 10:11 AM, Michał Marczyk
>

[Michał Marczyk]

On 21 April 2010 19:57, Sean Devlin <francoi...@gmail.com> wrote:
> If you're gonna over engineer use a protocol :-p

You're absolutely right, of course; I stand corrected! Here's my new
attempt at overengineering then:

(defprotocol Rotator
(rotate [self s]))

(extend-protocol Rotator
Number
(rotate
[self s]
(let [[front back] (split-at (mod self (count s)) s)]
(concat back front)))
clojure.lang.IFn
(rotate
[self s]
(let [[front back] (split-with self s)]
(concat back front))))

Funnily enough, I actually find this vaguely reasonable. :-)

[Michał Marczyk]

On 21 April 2010 20:09, Mark Engelberg <mark.en...@gmail.com> wrote:
> In some languages, split-at is more performant than doing take and
> drop separately.  But in Clojure, split-at is simply defined as:
> (defn split-at
>  "Returns a vector of [(take n coll) (drop n coll)]"
>  [n coll]
>    [(take n coll) (drop n coll)])
>
> So by using split-at, you gain nothing other than the additional
> overhead of constructing a vector and then turning around and
> destructuring it.

I realise that, however I find that there is also a slight gain in
readability / aesthetic appeal of the code; buying that at the minute
cost incurred due to creating and destructuring a vector seems
acceptable to me.

As an aside, it might actually be possible to write a more efficient
split-at -- perhaps exploiting the nature of the sequence being split
(e.g. you could use (seq (subvec ...)) with vectors) -- should the
need arise, so maybe it will become beneficial from the performance
POV at some point...

Sincerely,
Michał

[Per Vognsen]

Yet another variation:

(defn conjugate [f g & [g-inv]]
(comp (or g-inv g) f g))

(defn composite [f f-inv n x]
(nth (iterate (if (pos? n) f f-inv) x) (abs n)))

(defn rotate-left [xs]
(when (seq xs) (concat (rest xs) [(first xs)])))

(def rotate-right (conjugate rotate-left reverse))

(defn rotate [n xs]
(composite rotate-left rotate-right n xs))

This is intended to expose certain symmetries.

One of the basic ideas in mathematics is that an invertible
transformation T acts on elements by application, so that x becomes
T(x), and on functions by conjugation, so that f becomes T^(-1) . f .
T.

Another basic idea is that iterated compositions are like powers: f^n
is the n-fold composition of f. This is what iterate tries to capture.
This is meaningful for negative values of n when f is invertible. This
is what composite tries to capture.

If there were more direct support for doubly-infinite sequences (a fun
little programming exercise) then composite could return a
doubly-infinite sequence (much like iterate returns a singly-infinite
sequence), take would work with negative arguments, next would have a
counterpart prev, etc. Another fun exercise is to provide more direct
support for invertible functions. An invertible function can be
represented by a pair of functions. It implements IFn by applying the
first element of the pair. Inverting is just a matter of swapping the
elements.

Food for thought. :)

-Per

[Michał Marczyk]

On 22 April 2010 03:51, Per Vognsen <per.v...@gmail.com> wrote:
> Yet another variation:
>
> [...]
>
> Food for thought. :)

This is absolutely beautiful. I feel a tremendous joy now. :-)

Sincerely,
Michał

[Per Vognsen]

By the way, once you start looking for conjugation in common code
patterns, you see it everywhere. A less trivial example is the
Schwartzian transform for caching sorting keys:

(defn schwartz [key-fn] #(map (fn [x] [(key-fn x) x]) %))

(def unschwartz #(map second %))

(defn schwartz-sort [key-fn] (conjugate sort (schwartz key-fn) unschwartz))

If you implement first-class support for invertible functions
(surprisingly easy), you can capture important properties such as:

- composing invertible functions gives an invertible function.
- the inverse of an invertible function is an invertible function.

From this, it follows (with no extra work) that the conjugate
transformation of an invertible function is an invertible function.

-Per

[Harvey Hirst]

> (defn rotate [n s]
>  (let [[front back] (split-at (mod n (count s)) s)]
>    (concat back front)))

Don't forget (mod n 0) is an ArithmeticException.

Harvey

[Sean Devlin]

Oh wow... totally would have :)

[Nathan Rogers]

(defn rotate [a n]                                    
  (let [l (count a)                                    
        off (mod (+ (mod n l) l) l)]                  
    (flatten (list (drop off a) (take off a)))))    

(rotate '(1 2 3 4 5)  -1) => (5 1 2 3 4)
(rotate '(1 2 3 4 5)  -6) => (5 1 2 3 4)
(rotate '(1 2 3 4 5)   3) => (4 5 1 2 3)
(rotate '(1 2 3 4 5) 103) => (4 5 1 2 3)
(rotate '(1 2 3 4 5)   2) => (3 4 5 1 2)
(rotate '(1 2 3 4 5)   7) => (3 4 5 1 2)

Rotates any number of times
Handles zero with no conditional

n can be larger than the length and it will map correctly 

Negative n rotates right, Positive n rotates left
 

[Matching Socks]

Could it finish off the result in some way other than flatten?  flatten would go too far if the input data were a collection of collections. 

Indeed, I would support adding (some form of) rotate to the standard library on the condition that flatten be removed.  rotate is an amusement, but flatten is unexploded ordnance.

[Nathan Rogers]

(defn rotate [a n]                            

  (let [l (count a)                           

        off (mod (+ (mod n l) l) l)]          

    (concat (drop off a) (take off a)))) 

(rotate '((1 2) (3 4) (5 6) (7 8) (9 10)) 3)

=>   ((7 8) (9 10) (1 2) (3 4) (5 6))    

[kanishk kumar]

Testing with this, gives the wrong result

(rotate 6 [1 2 3 4 5]) Expected Output: [2 3 4 5 1] Actual Output: [1 2 3 4 5]

clo...@googlegroups.com