CODEWITHSUNDEEP
scalastream
jimakos17
jimakos17

Reputation: 935

Stream causes OutOfMemoryError in Scala

When I use a List it works correctly but when I create an infinite Stream

def foo = {
    val s = Stream.from(1)
    s.flatMap(x =>
                s.flatMap(y =>
                    s.flatMap(z => f(x, y, z))))
}

I'm getting a java.lang.OutOfMemoryError when I call 

foo.take(10)

As relates to f 

    def f(x: Int, y: Int, z: Int) = {
       if(Math.pow(x, 2) + Math.pow(y, 2) == Math.pow(z, 2) )
       else None
    }

Initially, I thought that it will be evaluated only when I would call it for these 10 elements but know I'm not sure. I'm getting the same problem with Iterator.from(1) Any help please. Thank you in advance!

Upvotes: 1

Views: 125

Answers (2)

AmigoNico
AmigoNico

Reputation: 6852

It looks like you are trying to generate triples in which the first member is greater than the second. To start, let's generate some pairs like that:

scala> def natNums = Iterator from 1
natNums: Iterator[Int]

scala> def foo = for { x <- natNums; y <- 1 until x } yield (x,y)
foo: Iterator[(Int, Int)]

scala> (foo take 15).toList
res4: List[(Int, Int)] = List((2,1), (3,1), (3,2), (4,1), (4,2), (4,3), (5,1), (5,2), (5,3), (5,4), (6,1), (6,2), (6,3), (6,4), (6,5))

Am I on the right track?

OK, now you want to add in a third member to the tuple. Well, if we similarly constrain z to be less than y, it works fine:

scala> def foo = for { x <- natNums; y <- 1 until x; z <- 1 until y } yield (x,y,z)
foo: Iterator[(Int, Int, Int)]

scala> (foo take 15).toList
res1: List[(Int, Int, Int)] = List((3,2,1), (4,2,1), (4,3,1), (4,3,2), (5,2,1), (5,3,1), (5,3,2), (5,4,1), (5,4,2), (5,4,3), (6,2,1), (6,3,1), (6,3,2), (6,4,1), (6,4,2))

But if z is unconstrained, I don't understand what you want the program to do. Just drawing z from natNums turns the CPU into a toaster:

scala> def foo = for { x <- natNums; y <- 1 until x; z <- natNums } yield (x,y,z)
foo: Iterator[(Int, Int, Int)]

scala> (foo take 15).toList
^C

Can you give us the output you are expecting?

UPDATE: Ah! Pythagorean triples -- how fun!

Here is a simple generator for what I'll call "raw" Pythagorean triples because it includes multiples which need to be filtered out. For example, (6,8,10) should not be counted as a Pythagorean triple since it is a multiple of (3,4,5). I'll leave that for you since I think what was blocking you was just the part about generating the numbers in the first place. Feel free to ask for help with that in another StackOverflow question if you need it.

scala> def rawPythagTriples =
   for { c <- Iterator from 1; a <- 1 until c; b <- a until c if a*a + b*b == c*c }
     yield (a,b,c)
rawPythagTriples: Iterator[(Int, Int, Int)]

scala> (rawPythagTriples take 10).toList
res2: List[(Int, Int, Int)] = List((3,4,5), (6,8,10), (5,12,13), (9,12,15), (8,15,17), (12,16,20), (7,24,25), (15,20,25), (10,24,26), (20,21,29))

Note that we begin with the hypotenuse, thus constraining a and b. By the way, you could make some minor optimizations, e.g. starting c at 5, a at 2, and b at a+1.

Upvotes: 2

user4322779
user4322779

Reputation:

This works in REPL:

def foo = {
  val s = Stream.from(1)
  s.flatMap(x =>
    s.flatMap(y =>
      s.flatMap(z => List(x,y,z))))
}

scala> foo.take(15) mkString ", "
res24: String = 1, 1, 1, 1, 1, 2, 1, 1, 3, 1, 1, 4, 1, 1, 5

Your f(x,y,z) must return a type that extends a subclass of GenTraversableOnce[?].

Upvotes: 0

Related Questions