N-dimensional `find`

#1

Given a traversable (sorry I don’t know which is the most general class) such as Set or List, I can use find to identify an element for which a given unary predicate f is satisfied, or whether such an element exists. However, given a binary predicate,g:(A,B)=>Boolean how can I find the first (or any I don’t really care whether it is the first or not) element, (a,b) in A x B, such that g(a,b) == true ? I.e., some a in A and b in B for which g(a,b)==true?

I can determine whether such exists using something like

A.exists(a => B.exists( b => g(a,b)))

And I could use two var variables to track a and b. Then if the outer exists returns true, then the tracking variables identify the pair. Is that the correct way?

  def findAxB[U,V](A:List[U],B:List[V],g:(U,V)=>Boolean):Option[(U,V)] = {
    var aa: U = A.head
    var bb: V = B.head
    if (A.exists { a: U => {
      aa = a
      B.exists { b: V => {
        bb = b
        g(a, b)
      }
      }
    }
    }
    )
      Some((aa, bb))
    else
      None
  }

This could of course be optimized a bit using find/exists rather than exists/exists.

#2

Just use find on the cartesian product.

#3

@martijnhoekstra, are you suggesting I compute the cartesian product? … even if g(A.head,B.head) is true?

#4

Another version. BTW it is bizarre how IntelliJ wants to indent the closing braces and parens.

  def findAxB[U,V](A:List[U],B:List[V],g:(U,V)=>Boolean):Option[(U,V)] = {
    if (A == Nil || B == Nil)
      None
    else {
      var aa = A.head
      var bb = B.head
      if (A.exists { a: U => {
        aa = a
        B.find { b: V => g(a, b) } match {
          case None => false
          case Some(b) => {
            bb = b
            true
          }
        }
      }
      }
      )
        None
      else
        Some((aa, bb))
    }
  }
#5

Yes, though probably lazily. Stream would be good datastructure for this. You could also use an iterator.

val it = for {
  a1 <- l1.iterator
  a2 <- l2.iterator
} yield (a1, a2)

it.find(predicate)
3 Likes
#6

@martijnhoekstra, I must say that that’s a nice solution. indeed.

#7

@martijnhoekstra, can you help me generalize your clever iterator solution to a slightly different problem. The following code seems to compile correctly, but it is not obvious to me whether truthTableToBdd is called once per outer iteration, or whether the (xxx until yyy).map forces a long iteration to occur before it’s wrapped into another iterator. Sorry if my question doesn’t make sense.

  def allBdds(numVars:Int):Iterator[Bdd] = {
    //  upper is the double exponential of numVars  i.e., 2^2^numVars, numVars is normally "small"
    // upper is the number of truth tables having numVars number of variables
    val upper:Long = scala.math.pow(2,scala.math.pow(2,numVars).toInt).toLong
    
    (0 until upper).map(j => truthTableToBdd(numVars,j)).iterator
  }
#8

I’m not entirely sure how much your current version evaluates: it will depend on how map is implemented exactly on Range.

pushing the call to iterator up will fix that for sure

(0 until upper).iterator.map(j => truthTableToBdd(numVars,j))

or with a Stream (in 2.13.x a LazyList) you dould do the same (0 until upper).toStream.map(j => truthTableToBdd(numVars,j))

#9

I can accept that you are right without understanding it, but isn’t (0 until upper) already an iterator? if I call the iterator method of an iterator, isn’t that just a NO-OP?

#10

no, (0 until upper) is a scala.lang.immutable.Range – it’s a description of the range only.

1 Like
#11

can I use a long inside a range? I get the following compiler error.

Error:(35, 14) type mismatch;
 found   : Long
 required: Int
    (0 until upper).iterator.map(j => truthTableToBdd(numVars,j))

Here’s the code.

  def allBdds(numVars:Int):Iterator[Bdd] = {
    val upper:Long = scala.math.pow(2,scala.math.pow(2,numVars).toInt).toLong

    (0 until upper).iterator.map(j => truthTableToBdd(numVars,j))
  }
  def truthTableToBdd(numVars:Int,truthTable:Long):Bdd = {
    // truthTable is interpreted as a stream of bits, with the least-significant-bit
    // being the top row of the truth table where all the variables are false.
    // truth table runs from 0000, 0001, 0010, 0011, ..., 1110, 1111
    // We iterate over the bits, and for those which are 1, we generate an
    // And() Bdd, and Or() all the results together.
    bitsToSet(truthTable)
      .map(_ - 1)
      .foldLeft(BddFalse:Bdd) { (b: Bdd, minterm: Int) =>
        Or(b, minTermToBdd(numVars,minterm))
      }
  }
#12

Yes, if you use a Long on the lhs:

0L until upper

If you start with an Int, until also expects an Int on the rhs (see RichInt.until) and a Long is not automatically promoted to Int since it is not a widening conversion.

2 Likes
#13

Can someone explain this error to me?

(0L until 4294967296L).iterator

I get the following error. Can I only create an iterator of a range if the range itself has fewer then Int.MaxValue elements? is Int.MaxValue an Int or a Long ? Does it really need to allocate Int.MaxValue many elements?

java.lang.IllegalArgumentException: More than Int.MaxValue elements.

java.lang.ExceptionInInitializerError
	at Main.main(main.scala)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:498)
	at sbt.Run.invokeMain(Run.scala:98)
	at sbt.Run.run0(Run.scala:92)
	at sbt.Run.execute$1(Run.scala:68)
	at sbt.Run.$anonfun$run$4(Run.scala:80)
	at scala.runtime.java8.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:12)
	at sbt.util.InterfaceUtil$$anon$1.get(InterfaceUtil.scala:10)
	at sbt.TrapExit$App.run(TrapExit.scala:253)
	at java.lang.Thread.run(Thread.java:748)
Caused by: java.lang.IllegalArgumentException: More than Int.MaxValue elements.
	at scala.collection.immutable.NumericRange$.check$1(NumericRange.scala:318)
	at scala.collection.immutable.NumericRange$.count(NumericRange.scala:328)
	at scala.collection.immutable.NumericRange.numRangeElements$lzycompute(NumericRange.scala:53)
	at scala.collection.immutable.NumericRange.numRangeElements(NumericRange.scala:52)
	at scala.collection.immutable.NumericRange.length(NumericRange.scala:55)
	at scala.collection.IndexedSeqLike.iterator(IndexedSeqLike.scala:90)
	at scala.collection.IndexedSeqLike.iterator$(IndexedSeqLike.scala:90)
	at scala.collection.immutable.NumericRange.iterator(NumericRange.scala:42)
	at Playground.<init>(main.scala:3)
	at Main$.<init>(main.scala:7)
	at Main$.<clinit>(main.scala)
	... 13 more
#14

IMO that’s a bug, though others may fight me on that.

:boxing_glove:

#15

Should I file a bug report?
It’d be my first scala bug. :slight_smile:

#16

https://github.com/scala/bug/issues/5619 - by design, wontfix :confused:

You could use something like Stream.range(0L, 4294967296L, 1L), but you may run into Int restrictions there at some point, as well.

1 Like
#17

Meh, I’m not to sure. I dont think there is a good reason empty should throw, and it seems an implementation detail of evaluating length. There is no fundamental reason it should.

#18

I’m fairly sure the reason this throws an exception is because such a Range would not be able to fulfill the IndexedSeq contract. Range extends IndexedSeq, and every element of an IndexedSeq must have an Int-valued index. By the “cubby hole principle” we know that if there is a set with more than Int.MaxValue elements, there is no surjection from the set of elements to Int. That is, the elements cannot all have unique indexes assigned to them. So a Range whose size is > Int.MaxValue could not fulfill the IndexedSeq contract.

Brian Maso

2 Likes
#19

If you only want an iterator you can use that instead:
Iterator.iterate(0L)(_ + 1).takeWhile(_ < 123456789123456789L)

One big difference between a Range and an Iterator is that Range is an immutable structure, while Iterator tracks its iteration status. You can iterate over a Range multiple times, but Iterator exhausts after first iteration and then it’s useless.