Recursive stream not behaving like I'd expect from Haskell

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Recursive stream not behaving like I'd expect from Haskell

August Alm
Hi!

This is my first post. I have some experience with Haskell but am new to Scala. Consider the number sequence u(n) defined recursively by u(0)=1, u(1)=1 and
u(n) = u(n - u(n-1)) + u(n - u(n-2)) for n > 1.
For example, u(2) = u(2 - u(1)) + u(2 - u(0)) = u(1) + u(1) = 2. In Haskell I implement this sequence as

us :: [Int]
us = 1 : 1 : map go [3..]
  where
    go n = let (s, t) = (us !! (fromIntegral n - 2), us !! (fromIntegral n - 3))
           in (us !! (n - s - 1)) + (us !! (n - t - 1))

My translation to Scala is

def us: Stream[Int] = {
   1 #:: 1 #:: from(3).map(n => us(n - us(n-2) - 1) + us(n - us(n-3) - 1))
 }

Nice and succinct! However, it seems the Scala code does not lend itself to evaluation in the way that I expect coming from Haskell. Consider the following Haskell function based on the sequence:

usGreaterThan :: Int -> Int -> Int
usGreaterThan n k
  | n<1        = 0
  | otherwise  = length . filter (>= k) $ take n us

The function tells us how many of the first n u's that are at least equal to k. My Scala translation is:

def usGreaterThan(n: Int, k: Int): Int = {
  if(n < 1){
     0
  }
  else{
    usTo(n).filter(k <= _).length
  }
}

The two give identical answers but the Haskell version is MUCH quicker. For n=1956 and k=602 the answer ought to be 770 but the Scala implementation never grinds to a halt.

Can someone explain why the languages behave so differently? And what is the smartest way to implement the solution in Scala?

Best wishes,
August

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Recursive stream not behaving like I'd expect from Haskell

Patrick Roemer-2
Responding to August Alm:

> Consider the number sequence u(n) defined recursively by u(0)=1,
> u(1)=1 and
> u(n) = u(n - u(n-1)) + u(n - u(n-2)) for n > 1.
> For example, u(2) = u(2 - u(1)) + u(2 - u(0)) = u(1) + u(1) = 2. In Haskell
> I implement this sequence as
>
> us :: [Int]
> us = 1 : 1 : map go [3..]
>   where
>     go n = let (s, t) = (us !! (fromIntegral n - 2), us !! (fromIntegral n
> - 3))
>            in (us !! (n - s - 1)) + (us !! (n - t - 1))
>
> My translation to Scala is
>
> def us: Stream[Int] = {
>    1 #:: 1 #:: from(3).map(n => us(n - us(n-2) - 1) + us(n - us(n-3) - 1))
>  }
>
> Nice and succinct! However, it seems the Scala code does not lend itself to
> evaluation in the way that I expect coming from Haskell.

"us" is declared as a function definition. Thus, every application of
"us" will trigger a completely new computation of the stream. Try "val
us" instead of "def us".

Best regards,
Patrick


--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Recursive stream not behaving like I'd expect from Haskell

August Alm


Den tisdag 27 december 2016 kl. 18:15:31 UTC+1 skrev Patrick Roemer:
Responding to August Alm:

> Consider the number sequence u(n) defined recursively by u(0)=1,
> u(1)=1 and
> u(n) = u(n - u(n-1)) + u(n - u(n-2)) for n > 1.
> For example, u(2) = u(2 - u(1)) + u(2 - u(0)) = u(1) + u(1) = 2. In Haskell
> I implement this sequence as
>
> us :: [Int]
> us = 1 : 1 : map go [3..]
>   where
>     go n = let (s, t) = (us !! (fromIntegral n - 2), us !! (fromIntegral n
> - 3))
>            in (us !! (n - s - 1)) + (us !! (n - t - 1))
>
> My translation to Scala is
>
> def us: Stream[Int] = {
>    1 #:: 1 #:: from(3).map(n => us(n - us(n-2) - 1) + us(n - us(n-3) - 1))
>  }
>
> Nice and succinct! However, it seems the Scala code does not lend itself to
> evaluation in the way that I expect coming from Haskell.

"us" is declared as a function definition. Thus, every application of
"us" will trigger a completely new computation of the stream. Try "val
us" instead of "def us".

Best regards,
Patrick

Thank you!
That did indeed make it "reasonably" behaved. I now wonder: What would be the difference between "val" and "lazy val" in this context of runtime optimization? (Since streams are already lazy the distinction is unclear to me.)
Best wishes,
Augsut

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Recursive stream not behaving like I'd expect from Haskell

Patrick Roemer-2
Responding to August Alm:

> Den tisdag 27 december 2016 kl. 18:15:31 UTC+1 skrev Patrick Roemer:
>> > us :: [Int]
>> > us = 1 : 1 : map go [3..]
>> >   where
>> >     go n = let (s, t) = (us !! (fromIntegral n - 2), us !! (fromIntegral
>> n
>> > - 3))
>> >            in (us !! (n - s - 1)) + (us !! (n - t - 1))
>> >
>> > My translation to Scala is
>> >
>> > def us: Stream[Int] = {
>> >    1 #:: 1 #:: from(3).map(n => us(n - us(n-2) - 1) + us(n - us(n-3) -
>> 1))
>> >  }
>> >
>> > Nice and succinct! However, it seems the Scala code does not lend itself
>> to
>> > evaluation in the way that I expect coming from Haskell.
>>
>> "us" is declared as a function definition. Thus, every application of
>> "us" will trigger a completely new computation of the stream. Try "val
>> us" instead of "def us".
>>
> Thank you!
> That did indeed make it "reasonably" behaved. I now wonder: What would be
> the difference between "val" and "lazy val" in this context of runtime
> optimization? (Since streams are already lazy the distinction is unclear to
> me.)

The problem with the "def" version was not lack of laziness, but
re-computation of of stuff that had already been evaluated. A
"translation" to Haskell:

<snip>
us' :: () -> [Int]
us' _ = 1 : 1 : map go [3..]
  where
    go n = let (s, t) = (us' () !! (n - 2), us' () !! (n - 3))
           in (us' () !! (n - s - 1)) + (us' () !! (n - t - 1))
</snip>

In Scala streams, it's the tail that's lazy. With "val", the actual
Stream cons (and its head!) will be materialized immediately; with "lazy
val", it will only be materialized upon first access.

<snip>
object StreamMain extends App {

  def dump(msg: String, s: Stream[Int]): Unit =
    println(s"$msg: ${s.take(3).toList}")

  println("instantiate")

  val usV: Stream[Int] = {
    println("usV init")
    1 #:: 1 #:: Stream.from(3).map(n =>
        usV(n - usV(n-2) - 1) + usV(n - usV(n-3) - 1))
  }

  lazy val usL: Stream[Int] = {
    println("usL init")
    1 #:: 1 #:: Stream.from(3).map(n =>
        usL(n - usL(n-2) - 1) + usL(n - usL(n-3) - 1))
  }

  def usD: Stream[Int] = {
    println("usD init")
    1 #:: 1 #:: Stream.from(3).map(n =>
        usD(n - usD(n-2) - 1) + usD(n - usD(n-3) - 1))
  }

  println("access")

  for(i <- 1 to 2) {
    dump(s"usV #$i", usV)
    dump(s"usL #$i", usL)
    dump(s"usD #$i", usD)
  }

}
</snip>

Output:

<snip>
instantiate
usV init
access
usV #1: List(1, 1, 2)
usL init
usL #1: List(1, 1, 2)
usD init
usD init
usD init
usD init
usD init
usD #1: List(1, 1, 2)
usV #2: List(1, 1, 2)
usL #2: List(1, 1, 2)
usD init
usD init
usD init
usD init
usD init
usD #2: List(1, 1, 2)
</snip>

Best regards,
Patrick


--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.