Iterator.unfold is missing

[julienrf]

See this post for a motivation: https://contributors.scala-lang.org/t/which-operations-should-be-included-in-the-new-collections/1106/75

In short: LazyList has un unfold but since it memoizes its elements it’s not memory efficient. We should either implement it in a GC-friendly way or simply add unfold to the Iterator companion.

[LPTK]

Yes! Iterator.unfold should definitely be added even if LazyList.unfold is made more efficient, as the iterator version will still probably be much faster. And I've often wondered why this method (which seems very important to me) does not exist yet.

Corollary: can we have Iterable.unfold too, which wraps Iterator.unfold into a stateless interface? I prefer avoiding Iterators as much as possible, as they expose users to implicit state.

[NthPortal]

@LPTK do you think init should be by-name for that?

[LPTK]

@NthPortal you made me check, and I was surprised to see that LazyList.unfold's init argument is not by name (which seems inconsistent with LazyLists generally being lazy in their head), and neither is your implementation of Iterator.unfold. IMHO they should all have by-name init...

[tarsa]

init argument is not the first element, but it is used to compute the first element. Therefore I think that we do not need to have initial state passed by name. Problem is different. LazyList factory forces computation of first element because it always calls Iterator.hasNext. Check it:

import scala.collection.AbstractIterator

object Laziness extends App {
  def unfoldIterator[A, S](init: S)(f: S => Option[(A, S)]): Iterator[A] = {
    var currentState = init
    var nextResultAndState: Option[(A, S)] = null

    new AbstractIterator[A] {
      override def hasNext: Boolean = {
        if (nextResultAndState == null) {
          nextResultAndState = f(currentState)
        }
        nextResultAndState.isDefined
      }

      override def next(): A = {
        assert(hasNext)
        val (result, state) = nextResultAndState.get
        currentState = state
        nextResultAndState = null
        result
      }
    }
  }

  val lazyList1 = LazyList.unfold(5) { _ =>
    println("lazy list generator invoked")
    None
  }
  val iterator = unfoldIterator(5) { _ =>
    println("iterator generator invoked")
    None
  }
  println("before converting")
  val lazyList2 = iterator.to(LazyList)
  println("after converting")
  lazyList2.headOption
  println("after inspecting")
}

Probably unfolding LazyList and creating LazyList from Iterator needs some additional lazy wrappers.

OTOH, Iterator based unfold could be used to implement unfold for all collections. See this:

import scala.collection.immutable.WrappedString
import scala.collection.{AbstractIterator, Factory, IterableFactory}
import scala.language.higherKinds

object UnfoldOps extends App {
  implicit class CollectionUnfoldOps1[A, C](factory: Factory[A, C]) {
    def unfold[S](init: S)(f: S => Option[(A, S)]): C =
      factory.fromSpecific(unfoldIterator(init)(f))
  }

  implicit class CollectionUnfoldOps2[C[_]](factory: IterableFactory[C]) {
    def unfold[A, S](init: S)(f: S => Option[(A, S)]): C[A] =
      factory.fromSpecific(unfoldIterator(init)(f))
  }

  def unfoldIterator[A, S](init: S)(f: S => Option[(A, S)]): Iterator[A] = {
    var currentState = init
    var nextResultAndState: Option[(A, S)] = null

    new AbstractIterator[A] {
      override def hasNext: Boolean = {
        if (nextResultAndState == null) {
          nextResultAndState = f(currentState)
        }
        nextResultAndState.isDefined
      }

      override def next(): A = {
        assert(hasNext)
        val (result, state) = nextResultAndState.get
        currentState = state
        nextResultAndState = null
        result
      }
    }
  }

  val initialState = 5
  val generator = (state: Int) =>
    if (state < 10) Some((state.toChar, state + 1)) else None

  LazyList.unfold(initialState)(generator)
  Vector.unfold(initialState)(generator)
  WrappedString.unfold(initialState)(generator)
  Iterable.unfold(initialState)(generator)
}

Both code examples are for Scala 2.13.0-M4

Update:
Lazy unfold could be implemented using existing unfolds. Here is the code:

  def lazierUnfold[A, S](init: => S)(f: S => Option[(A, S)]): LazyList[A] =
    LazyList.unfold(() => init)(ff => f(ff()).map(p => (p._1, () => p._2)))

Someone could want to go deeper and demand signature like:

  def laziestUnfold[A, S](init: => S)(f: S => Option[(A, => S)]): LazyList[A]

which could be implemented similarly.