[scala] How would you write Stream.cycle?

[Paul Chiusano-2]

I am trying to write a function which cycles a Stream, s, that is,
forms the infinite stream s ++ s ++ ... Is it possible to do this
without writing a custom Stream implementation?

Here was my first attempt:

 def cycle[E](s: => Stream[E]): Stream[E] = {
      lazy val stream = s
      stream.append(cycle(stream))
 }

Nope! This bombs with a stack overflow. I was hoping it would work
just like Haskell:

Prelude> let cycle x = x ++ cycle x
Prelude> take 11 (cycle [1,2,3,4])
[1,2,3,4,1,2,3,4,1,2,3]

But Stream.append evaluates its argument fully, so that leads to
infinite recursion.

Is there any way to do this in Scala and at least keep the spirit of
the Haskell version?

Paul

[Jamie Webb-2]

On 2008-07-09 17:53:50 Paul Chiusano wrote:

> I am trying to write a function which cycles a Stream, s, that is,
> forms the infinite stream s ++ s ++ ... Is it possible to do this
> without writing a custom Stream implementation?
>
> Here was my first attempt:
>
>  def cycle[E](s: => Stream[E]): Stream[E] = {
>       lazy val stream = s
>       stream.append(cycle(stream))
>  }
>
> Nope! This bombs with a stack overflow.

Works for me. Post a full test case?

> I was hoping it would work
> just like Haskell:
>
> Prelude> let cycle x = x ++ cycle x
> Prelude> take 11 (cycle [1,2,3,4])
> [1,2,3,4,1,2,3,4,1,2,3]
>
> But Stream.append evaluates its argument fully, so that leads to
> infinite recursion.

No, it doesn't.

> Is there any way to do this in Scala and at least keep the spirit of
> the Haskell version?

You can simplify to just:

  def cycle[T](s : Stream[T]) : Stream[T] = s append cycle(s)

Thus:

  Welcome to Scala version 2.7.1.final (Java HotSpot(TM) Server VM, Java
  1.6.0_03). Type in expressions to have them evaluated.
  Type :help for more information.

  scala> val s = List(1,2,3).toStream
  s: Stream[Int] = Stream(1, 2, 3)

  scala> def cycle[T](s : Stream[T]) : Stream[T] = s append cycle(s)
  cycle: [T](Stream[T])Stream[T]

  scala> cycle(s) take 10 toList
  res0: List[Int] = List(1, 2, 3, 1, 2, 3, 1, 2, 3, 1)

/J

[liesen]

Paul Chiusano-2 wrote:

I am trying to write a function which cycles a Stream, s, that is,
forms the infinite stream s ++ s ++ ... Is it possible to do this
without writing a custom Stream implementation?

Here was my first attempt:

 def cycle[E](s: => Stream[E]): Stream[E] = {
      lazy val stream = s
      stream.append(cycle(stream))
 }

Nope! This bombs with a stack overflow. I was hoping it would work
just like Haskell:

Prelude> let cycle x = x ++ cycle x
Prelude> take 11 (cycle [1,2,3,4])
[1,2,3,4,1,2,3,4,1,2,3]

But Stream.append evaluates its argument fully, so that leads to
infinite recursion.

That's odd. I specified cycle the same way you did:

def cycle[A](xs: Stream[A]): Stream[A] = s append cycle(s)

... and set up an infinite stream like this:

def from(n: Int): Stream[Int] = Stream.cons(n, from(n + 1))

I have no problems running cycle(from(1)) or cycle(from(n) take m)...

[Paul Chiusano-2]

You're right. My test case was bad. I was supplying an empty list,
which DOES cause a stack overflow.

Thanks.

On Wed, Jul 9, 2008 at 6:24 PM, liesen <johanliesen@...> wrote:

>
>
>
> Paul Chiusano-2 wrote:
>>
>> I am trying to write a function which cycles a Stream, s, that is,
>> forms the infinite stream s ++ s ++ ... Is it possible to do this
>> without writing a custom Stream implementation?
>>
>> Here was my first attempt:
>>
>>  def cycle[E](s: => Stream[E]): Stream[E] = {
>>       lazy val stream = s
>>       stream.append(cycle(stream))
>>  }
>>
>> Nope! This bombs with a stack overflow. I was hoping it would work
>> just like Haskell:
>>
>> Prelude> let cycle x = x ++ cycle x
>> Prelude> take 11 (cycle [1,2,3,4])
>> [1,2,3,4,1,2,3,4,1,2,3]
>>
>> But Stream.append evaluates its argument fully, so that leads to
>> infinite recursion.
>>
>
> That's odd. I specified cycle the same way you did:
>
> def cycle[A](xs: Stream[A]): Stream[A] = s append cycle(s)
>
> ... and set up an infinite stream like this:
>
> def from(n: Int): Stream[Int] = Stream.cons(n, from(n + 1))
>
> I have no problems running cycle(from(1)) or cycle(from(n) take m)...
> --
> View this message in context: http://www.nabble.com/-scala--How-would-you-write-Stream.cycle--tp18371706p18372210.html
> Sent from the Scala mailing list archive at Nabble.com.
>
>

[David MacIver]

On Wed, Jul 9, 2008 at 11:19 PM, Jamie Webb <j@...> wrote:

> On 2008-07-09 17:53:50 Paul Chiusano wrote:
>> I am trying to write a function which cycles a Stream, s, that is,
>> forms the infinite stream s ++ s ++ ... Is it possible to do this
>> without writing a custom Stream implementation?
>>
>> Here was my first attempt:
>>
>>  def cycle[E](s: => Stream[E]): Stream[E] = {
>>       lazy val stream = s
>>       stream.append(cycle(stream))
>>  }
>>
>> Nope! This bombs with a stack overflow.
>
> Works for me. Post a full test case?
>
>> I was hoping it would work
>> just like Haskell:
>>
>> Prelude> let cycle x = x ++ cycle x
>> Prelude> take 11 (cycle [1,2,3,4])
>> [1,2,3,4,1,2,3,4,1,2,3]
>>
>> But Stream.append evaluates its argument fully, so that leads to
>> infinite recursion.
>
> No, it doesn't.
>
>> Is there any way to do this in Scala and at least keep the spirit of
>> the Haskell version?
>
> You can simplify to just:
>
>  def cycle[T](s : Stream[T]) : Stream[T] = s append cycle(s)

These have rather different sharing characteristics though. This
version uses a potentially unbounded amount of space, whereas the
original uses O(n) in the size of the original list.

[David MacIver]

On Thu, Jul 10, 2008 at 12:18 AM, David MacIver <david.maciver@...> wrote:

> On Wed, Jul 9, 2008 at 11:19 PM, Jamie Webb <j@...> wrote:
>> On 2008-07-09 17:53:50 Paul Chiusano wrote:
>>> I am trying to write a function which cycles a Stream, s, that is,
>>> forms the infinite stream s ++ s ++ ... Is it possible to do this
>>> without writing a custom Stream implementation?
>>>
>>> Here was my first attempt:
>>>
>>>  def cycle[E](s: => Stream[E]): Stream[E] = {
>>>       lazy val stream = s
>>>       stream.append(cycle(stream))
>>>  }
>>>
>>> Nope! This bombs with a stack overflow.
>>
>> Works for me. Post a full test case?
>>
>>> I was hoping it would work
>>> just like Haskell:
>>>
>>> Prelude> let cycle x = x ++ cycle x
>>> Prelude> take 11 (cycle [1,2,3,4])
>>> [1,2,3,4,1,2,3,4,1,2,3]
>>>
>>> But Stream.append evaluates its argument fully, so that leads to
>>> infinite recursion.
>>
>> No, it doesn't.
>>
>>> Is there any way to do this in Scala and at least keep the spirit of
>>> the Haskell version?
>>
>> You can simplify to just:
>>
>>  def cycle[T](s : Stream[T]) : Stream[T] = s append cycle(s)
>
> These have rather different sharing characteristics though. This
> version uses a potentially unbounded amount of space, whereas the
> original uses O(n) in the size of the original list.

Of course, now that I look at the pasted Haskell code (which I
foolishly assumed was equivalent to the pasted Scala code), this
perfectly captures the spirit of the original Haskell because that
uses a potentially unbounded amount of space too. Oh well. :-)

[tmorris]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Paul Chiusano wrote:
| I am trying to write a function which cycles a Stream, s, that is,
| forms the infinite stream s ++ s ++ ... Is it possible to do this
| without writing a custom Stream implementation?
|
| Here was my first attempt:
|
|  def cycle[E](s: => Stream[E]): Stream[E] = {
|       lazy val stream = s
|       stream.append(cycle(stream))
|  }
|
| Nope! This bombs with a stack overflow. I was hoping it would work
| just like Haskell:
|
| Prelude> let cycle x = x ++ cycle x
| Prelude> take 11 (cycle [1,2,3,4])
| [1,2,3,4,1,2,3,4,1,2,3]
|
| But Stream.append evaluates its argument fully, so that leads to
| infinite recursion.
|
| Is there any way to do this in Scala and at least keep the spirit of
| the Haskell version?
|
| Paul
|
|
|
Do note that Haskell is a little different, with early failure on []
instead of non-termination. In any case, this seems fine:

scala> def cycle[A](as: Stream[A]): Stream[A] = if(as.isEmpty)
error("cycle on empty") else as append cycle(as)
cycle: [A](Stream[A])Stream[A]

scala> cycle(cons(1, cons(2, cons(3, empty)))).head
res16: Int = 1

- --
Tony Morris
http://tmorris.net/

Real-world problems are simply degenerate cases of pure mathematical
problems.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFIdUytmnpgrYe6r60RAm6hAJ43l994LZHMkbCO0AsFUE/oV67rPQCgqQgW
/Vb6Hw1IzC1o7PNHTHTkS5U=
=qpdi
-----END PGP SIGNATURE-----

[Eric Willigers]

Tony Morris wrote:
> scala> def cycle[A](as: Stream[A]): Stream[A] = if(as.isEmpty)
> error("cycle on empty") else as append cycle(as)
> cycle: [A](Stream[A])Stream[A]

And to achieve sharing,

     def cycle[T](s : Stream[T]) : Stream[T] = {
         if (s.isEmpty)
             throw new UnsupportedOperationException("cycle on empty
stream")
         else
             new { val result : Stream[T] = s append result }.result
     }