Extension of interleave in clojure

Question

I want to write a function to interleave two given sequences. The function should work like this:

user=> (ext-interl '(1 2 3 4 5 6 7 8) '(a b c))
(1 a 2 b 3 c 4 a 5 b 6 c 7 a 8 b)

The process will end when it reaches the longer sequence.

My code is:

(defn ext-interl [l1 l2]
 (lazy-seq
  (let [ls1 (seq l1) ls2 (seq l2)]
    (cond (and ls1 ls2)
     (cons (first ls1) (cons (first ls2) (ext-interl (rest ls1) (rest ls2))))
     ls1 ls1
     ls2 ls2))))

But this code runs like:

 user=> (ext-interl '(1 2 3 4 5 6 7 8) '(a b c))
(1 a 2 b 3 c 4 5 6 7 8)

How can I fix this code? Thank you!

are you just practicing? if not, you could always do `(interleave [1 2 3 4 5 6 7 8] (cycle '[a b c]))` — Shlomi, May 02 '16 at 21:34
@Shlomi Thank you. I did not know the function cycle. Now I can figure it out. — Xiufen Xu, May 03 '16 at 01:14

Michał Marczyk · Accepted Answer · 2016-05-03T03:22:01.930

Here are three versions: a simple, strict one; a lazy one based on clojure.core combinators; and a lazy one based on the same combinators that takes an arbitrary number of inputs.

A simple strict approach

A sanity check on the lazy approaches.

(defn interleave-longer-strict [xs ys]
  (take (* 2 (max (count xs) (count ys)))
    (interleave (cycle xs) (cycle ys))))

Combinator-based lazy approach

This one is a lazy version based on map, mapcat, take-while, iterate, interleave and cycle:

(defn interleave-longer
  "Lazy version of

    (take (* 2 (max (count xs) (count ys)))
      (interleave (cycle xs) (cycle ys)))"
  [xs ys]
  (map (fn [_ e] e)
    (mapcat (fn [[xs ys]] [[xs ys] [xs ys]])
      (take-while (fn [[xs ys]] (or xs ys))
        (iterate (fn [[xs ys]] [(next xs) (next ys)])
          [xs ys])))
    (interleave (cycle xs) (cycle ys))))

To demonstrate that it is indeed lazy (NB. (range) never returns – if you actually consume it up through Long/MAX_VALUE, it'll just start returning clojure.lang.BigInts):

(take 30 (interleave-longer (range) (range 11)))
;= (0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 0 12 1 13 2 14 3)

(take 30 (interleave-longer (range 11) (range)))
;= (0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 0 11 1 12 2 13 3 14)

Combinator-based lazy approach with varargs

And finally, a lazy version based on the same primitives plus apply, repeat and count (applied to the varargs seq to establish how many inputs there are) that takes an arbitrary number of inputs:

(defn interleave-longest [& xss]
  (map (fn [e & _] e)
    (apply interleave (map cycle xss))
    (mapcat (fn [xss] (repeat (count xss) xss))
      (take-while (fn [xss] (some some? xss))
        (iterate (fn [xss] (mapv next xss))
          xss)))))

At the REPL:

(interleave-longest [:a :b :c :d] (range 11) '[x y z])
;= (:a 0 x :b 1 y :c 2 z :d 3 x :a 4 y :b 5 z :c 6 x :d 7 y :a 8 z :b 9 x :c 10 y)

(take 30 (interleave-longest [:a :b :c :d] (range) '[x y z]))
;= (:a 0 x :b 1 y :c 2 z :d 3 x :a 4 y :b 5 z :c 6 x :d 7 y :a 8 z :b 9 x)

Piotrek Bzdyl · Answer 2 · 2016-05-03T06:48:18.157

Your solution fails in your second and third cond clauses: when one of the sequences if fully used, you just append the remaining one to the end. You would need to probably call another function that would merge the remaining collection with the other one cycles from the beginning. For example:

(defn- ext-interleave' [orig-xs xs orig-ys ys]
  (let [xs (seq xs)
        ys (seq ys)]
    (cond
      (and xs ys)
      (concat
        [(first xs) (first ys)]
        (ext-interleave' orig-xs (rest xs) orig-ys (rest ys)))

      xs
      (interleave xs (cycle orig-ys))

      ys
      (interleave (cycle orig-xs) ys))))

(defn ext-interleave [xs ys]
  (ext-interleave' xs xs ys ys))

(ext-interleave [1 2 3 4 5 6 7 8] '[a b c])

This solution is mostly lazy (it eagerly consumes two first items from both sequences) in the first cond branch.

If you don't need a lazy solution, I would use existing functions to make this work:

cycle + take to make your sequences as long as needed
core interleave to combine them

Solution:

(defn ext-interleave [xs ys]
  (let [l (max (count xs) (count ys))
        xs (take l (cycle xs))
        ys (take l (cycle ys))]
    (interleave xs ys)))
(ext-interleave [1 2 3 4 5 6 7 8] '[a b c])
;; => (1 a 2 b 3 c 4 a 5 b 6 c 7 a 8 b)

You can even make it work for any number of input sequences:

(defn ext-interleave' [& cols]
  (let [l (apply max (map count cols))
        cols (map #(take l (cycle %)) cols)]
    (apply interleave cols)))

(ext-interleave' [1 2 3 4 5 6 7 8] '[a b c] [:y :z])
;; => (1 a :y 2 b :z 3 c :y 4 a :z 5 b :y 6 c :z 7 a :y 8 b :z)

The provided solution will not be lazy as count will force your input sequences to be realised in order to count their elements.

Note that `ext-interleave'` as currently written reverses the order in which elements are taken from `xs` and `ys` if `ys` is the longer sequence, starting at the point when `xs` first runs out. This is easily fixed by swapping around the arguments to `interleave` in the final branch of the `cond`. — Michał Marczyk, May 03 '16 at 00:09
@Piotrek Bzdyl. Thank you so much! Your solutions are very clear and easy to understand. However, I am wondering what is different between repeat and cycle. Since I read the API of repeat and cycle, they look like the same. — Xiufen Xu, May 03 '16 at 00:49
I have fixed my mistake. The difference between `cycle` and `repeat` is that `repeat` repeats single element whereas `cycle` will cycle element from the provided sequence. — Piotrek Bzdyl, May 03 '16 at 06:51

Extension of interleave in clojure

2 Answers2

A simple strict approach

Combinator-based lazy approach

Combinator-based lazy approach with varargs