# Recursive stream not behaving like I'd expect from Haskell

4 messages
Open this post in threaded view
|

## Recursive stream not behaving like I'd expect from Haskell

 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 asus :: [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 isdef 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 -> IntusGreaterThan n k  | n<1        = 0  | otherwise  = length . filter (>= k) \$ take n usThe 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.
Open this post in threaded view
|

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

 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.