verifying a probability distribution with variable arguments sums to 1

Question

I was wondering how you would write a method in Scala that takes a function f and a list of arguments args where each arg is a range. Suppose I have three arguments (Range(0,2), Range(0,10), and Range(1, 5)). Then I want to iterate over f with all the possibilities of those three arguments.

var sum = 0.0
for (a <- arg(0)) {
  for (b <- arg(1)) {
    for (c <- arg(2)) {
      sum += f(a, b, c)
    }
  }
}

However, I want this method to work for functions with a variable number of arguments. Is this possible?

Edit: is there any way to do this when the function does not take a list, but rather takes a standard parameter list or is curried?

Answer 1

That's a really good question!

You want to run flatMap in sequence over a list of elements of arbitrary size. When you don't know how long your list is, you can process it with recursion, or equivalently, with a fold.

scala> def sequence[A](lss: List[List[A]]) = lss.foldRight(List(List[A]())) {
     |    (m, n) => for (x <- m; xs <- n) yield x :: xs
     | }
scala> sequence(List(List(1, 2), List(4, 5), List(7)))
res2: List[List[Int]] = List(List(1, 4, 7), List(1, 5, 7), List(2, 4, 7), List(2
, 5, 7))

(If you can't figure out the code, don't worry, learn how to use Hoogle and steal it from Haskell)

You can do this with Scalaz (in general it starts with a F[G[X]] and returns a G[F[X]], given that the type constructors G and F have the Traverse and Applicative capabilities respectively.

scala> import scalaz._
import scalaz._

scala> import Scalaz._
import Scalaz._

scala> List(List(1, 2), List(4, 5), List(7)).sequence
res3: List[List[Int]] = List(List(1, 4, 7), List(1, 5, 7), List(2, 4, 7), List(2
, 5, 7))

scala> Seq(some(1), some(2)).sequence
res4: Option[Seq[Int]] = Some(List(1, 2))

scala> Seq(some(1), none[Int]).sequence
res5: Option[Seq[Int]] = None

Answer 2

That would more or less do the job (without applying f, which you can do separately)

  def crossProduct[A](xxs: Seq[A]*) : Seq[Seq[A]] 
    = xxs.foldLeft(Vector(Vector[A]())){(res, xs) => 
      for(r <- res; x <- xs) yield r :+ x
    }

You can then just map your function on that. I'm not sure it's a very efficient implementation though.