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)


No comments:

Post a Comment