Skip to content

Instantly share code, notes, and snippets.

@aloiscochard
Created November 2, 2011 16:06
Show Gist options
  • Save aloiscochard/1334040 to your computer and use it in GitHub Desktop.
Save aloiscochard/1334040 to your computer and use it in GitHub Desktop.
Scala [In]finite Stream Constructor
import Stream._
/** A possibly finite stream that repeatedly applies a given function to a start value.
*
* @param start the start value of the stream
* @param f the function that's repeatedly applied
* @return the stream returning the possibly finite sequence of values `start, f(start), f(f(start)), ...`
*/
def iterate[A](f: A => A, a: A): Stream[A] = unfold((x: A) => Some((x, f(x))), a)
def unfold[A, B](start: B)(f: B => Option[Tuple2[A,B]]): Stream[A] = f(start) match {
case Some((elem, next)) => elem #:: unfold(next)(f)
case None => empty
}
// Could be integrated here -> https://lampsvn.epfl.ch/trac/scala/browser/scala/tags/R_2_9_1_final/src//library/scala/collection/immutable/Stream.scala#L647
@missingfaktor
Copy link

Why not just use Stream.iterate?

scala> Stream.iterate(2)(2 *)
res29: scala.collection.immutable.Stream[Int] = Stream(2, ?)

scala> res29 take 10 toList
res30: List[Int] = List(2, 4, 8, 16, 32, 64, 128, 256, 512, 1024)

@aloiscochard
Copy link
Author

@missingfaktor because Stream.iterate only support infinite sequence, with my version you can stop by returning None

@missingfaktor
Copy link

Oh, I see. It's more similar to unfold from Scalaz.

scala> 5.unfold[Stream, Int](x => if(x < 100) Some(x * 2, x + 1) else None)
res41: Stream[Int] = Stream(10, ?)

scala> res41.toList
res42: List[Int] = List(10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 128, 130, 132, 134, 136, 138, 140, 142, 144, 146, 148, 150, 152, 154, 156, 158, 160, 162, 164, 166, 168, 170, 172, 174, 176, 178, 180, 182, 184, 186, 188, 190, 192, 194, 196, 198)

@aloiscochard
Copy link
Author

Ok, I'm reinventing scalaz here :-D ... Make sense, I had this idea while learning haskell!

But I still believe it should be in scala-core as presented here.

Thanks for pointing this out mate.

@missingfaktor
Copy link

Welcome, mate! Yes, I agree unfold is pretty basic, and deserves a place in the standard library.

@aloiscochard
Copy link
Author

I've just added unfold implementation which could be integrated in std lib

@cvogt
Copy link

cvogt commented Feb 23, 2015

@aloiscochard For what use case is unfold better than iterate?
@missingfaktor's example seems clearer using iterate rather than unfold
Stream.iterate(5)(+1).map(*2).takeWhile(x < 200)

@copumpkin
Copy link

@cvogt for anything where it doesn't make sense to keep asking for stuff indefinitely. In your example, +1 doesn't care if you keep running it forever, so you're safe with an intermediate infinite stream, but in many more realistic use cases, you have a process that you're going to have to repeat until some condition stops being true, and then you need to stop, and that's based on a piece of internal state that is no longer accessible by the time you use takeWhile. A simple example of a good use case here is a pagination API that hands you a "marker" telling you how to ask for more. You can't just keep asking for more forever and filter later.

Also, unfold is in some senses the most fundamental operation on a Stream, much like how fold (right) is a fundamental operation on List.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment