CODEWITHSUNDEEP
clojurelazy-evaluation
Mike Hogan
Mike Hogan

Reputation: 10603

first common element of potentially infinite sequences

I have written code to find the common elements of a number of sequences:

(defn common [l & others]
  (if (= 1 (count others)) 
    (filter #(some #{%1} (first others)) l) 
    (filter #(and (some #{%1} (first others)) (not (empty? (apply common (list %1) (rest others))))) l)))

which can find the first common element of finite sequences like this:

(first (common [1 2] [0 1 2 3 4 5] [3 1])) -> 1

but it is very easily sent on an infinite search if any of the sequences are infinite:

(first (common [1 2] [0 1 2 3 4 5] (range)))

I understand why this is happening, and I know I need to make the computation lazy in some way, but I can't yet see how best to do that.

So that is my question: how to rework this code (or maybe use entirely different code) to find the first common element of a number of sequences, one or more of which could be infinite.

Upvotes: 2

Views: 164

Answers (2)

user2263578
user2263578

Reputation: 215

I would probably do something like 

(fn [ & lists ]
    (filter search-in-finite-lists (map (fn [ & elements ] elements) lists)))

The trick is to search one level by level, in all lists at once. At each level, you need only search if the last element of each list is in any other list.

I guess it is expected to search infinitely if the list are infinite and there is no match. However, you could add a (take X lists) before the filter to impose a maximum. like so :

(fn [ max & lists ]
    (filter search-in-finite-lists (take max (map (fn [ & elements ] elements) lists))))

Well, that is still assuming a finite number of lists... Which shoud be reasonable.

Upvotes: 0

amalloy
amalloy

Reputation: 91907

This isn't possible without some other constraints on the contents of the sequence. For example, if they were required to be in sorted order, you could do it. But given two infinite, arbitrarily-ordered sequences A and B, you can't ever decide for sure that A[0] isn't in B, because you'll keep searching forever, so you'll never be able to start searching for A[1].

Upvotes: 4

Related Questions