Monday, 9 January 2012

List Split-At Function

Today's puzzle from the 4-Clojure site it to write a function that will split a list at a given numbered element - - so for example if you split the list (a b c d e) at 2 you get back the lists (a b) - first 2 elements - and the list (c d e) - the rest.

user=> (split-at 2 [:a :b :c :d :e])
[(:a :b) (:c :d :e)]

This is the same as the function split-at which is built in.

The simple solution is to observe that the first list you return is what you get by taking n items from the given list, and the second list is what you get by dropping n items from the list.  Take and drop functions are available already.  Putting that together the function we want looks like this:-

(fn [n xs] (list (take n xs) (drop n xs)))

Alternatively, if we want to do this the hard way, we can write a loop.  At the top of the loop we create a left-hand list, initially empty, and a right-hand list, also initially empty.  Then we scan through the source list item by item, counting our number n down as we go.  As long as n is over zero we add each element to the left hand list: when n drops to zero and below we add each item to the right hand list.  When the source list is finished we return the two new lists we just built.  So the function looks like this:-

(defn hard-split-at [n xs]
 (loop [ls [], rs [], n n, xs xs]
  (if (seq xs)
   (if (> n 0)
    (recur (cons (first xs) ls) rs (- n 1) (rest xs))
    (recur ls (cons (first xs) rs) (- n 1) (rest xs)))
   (list ls rs))))

No comments:

Post a Comment