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.
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))
}
}
@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
}
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?
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))
}
}
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.
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
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.
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.
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.
