 # 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. #15

Should I file a bug report?
It’d be my first scala bug. #16

https://github.com/scala/bug/issues/5619 - by design, wontfix 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.