Création d'un joint (1) -Memory Iterable d'un objet initial et une fonction qui génère l'objet suivant, dans Scala

Question

Je veux un moyen pratique de générer un Iterable, étant donné un objet initial et une fonction pour produire l'objet suivant de l'actuel, qui consomme O (1) la mémoire (par exemple, il ne cache pas des résultats anciens, si vous veulent itérer une seconde fois, la fonction doit être appliquée à nouveau).

Il ne semble pas comme il y a le soutien aux bibliothèques pour cela. Dans Scala 2.8, la méthode a scala.collection.Iterable.iterate signature

def iterate [A] (start: A, len: Int)(f: (A) ⇒ A) : Iterable[A]

donc il faut que vous spécifiez le nombre d'applications fonction itérée vous êtes intéressé à l'avance, et ma compréhension de la documentation est que Iterable.iterate calcule en fait toutes ces valeurs immédiatement. D'autre part, la méthode a scala.collection.Iterator.iterate signature

def iterate [T] (start: T)(f: (T) ⇒ T) : Iterator[T]

qui ressemble beaucoup, mais nous obtenons seulement une Iterator qui n'offre tout le confort de map, filter et amis.

  

Y at-il une méthode de bibliothèque pratique pour produire ce que je veux?

et sinon,

  

Quelqu'un peut-il suggérer le 'dialectal' le code Scala pour le faire?

En résumé, étant donné un objet initial a: A, et un f: A => A de fonction, je voudrais un TraversableLike (par exemple, probablement un Iterable) qui génère a, f(a), f(f(a)), ..., et utilise O (1) de mémoire, avec map, fonctions, etc. filter que retourner aussi quelque chose qui est O (1) dans la mémoire.

Answer 1

Iterator.iterate demo avec filtre:

object I {
  def main(args:Array[String]) {
    val mb = 1024 * 1024
    val gen = Iterator.iterate(new Array[Int](10 * mb)){arr => 
      val res = new Array[Int](10 * mb)
      arr.copyToArray(res)
      println("allocated 10mb")
      res(0) = arr(0) + 1 // store iteration count in first elem of new array
      res
    }
    // take 1 out of 100
    val gen2 = gen filter (arr => arr(0) % 100 == 0) 
    // print first 10 filtered
    gen2.take(10).foreach { arr => println("filtered " + arr(0)) } 
  }
}

(ce travail ne peut pas dans le REPL que l'étape d'impression peut gâcher la gestion de la mémoire)

JAVA_OPTS="-Xmx128m" scala -cp classes I montrera que les travaux de filtrage et est paresseux. Si elle n'a pas été fait en mémoire constante qui provoquerait une erreur de tas (car il est quelque chose comme 900 l'allocation * 10mb).

Utilisez JAVA_OPTS="-Xmx128m -verbose:gc" scala -cp classes I pour voir les événements de collecte des ordures.

Answer 2

Stream fera ce que vous voulez, il suffit de ne pas tenir sur les cellules; que itérer sur les valeurs.

Il est une idée fausse, malheureusement commun flottant autour de ce cours d'eau en cache en soi toutes les valeurs qu'ils calculent.

Si vous écrivez ceci:

val s1: Stream[Thing] = initialValue #:: «expression computing next value»

alors en effet à chaque valeur produite par le courant est conservé, mais ce n'est pas nécessaire. Si vous écrivez:

def s2: Stream[Thing] = initialValue #:: «expression computing next value»

et si l'appelant itère un peu plus les valeurs du flux, mais ne se souvient pas de la chaîne de valeur elle-même (en particulier l'une de ses cellules contre), puis la rétention ne se produira non désiré. Bien sûr, dans cette formulation, chaque appel crée une nouvelle Stream à partir d'une valeur initiale fixe. Ce n'est pas nécessaire:

def s3(start: Thing): Stream[Thing] = start #:: «expression computing next value»

La seule chose que vous devez regarder pour une passe Stream à une méthode. Cela permettra de saisir la tête du flux passé dans le paramètre de la méthode. Une façon de contourner cela est de traiter le flux avec le code récursif-queue.

Answer 3

Iterator est la chose que vous voulez. Et iterator do a carte, filtre, takeWhile et bien d'autres méthodes est O (1) memory.I ne pense pas qu'il y ait un autre type de collection avec O (1) dans la mémoire.

Answer 4

val it = new Iterable[Int] {
  def iterator = Iterator.iterate(0)(_+1)
  override
  def toString: String = "Infinite iterable"
}

Ne pas essayer sur REPL (sauf en l'intégrant à l'intérieur d'un objet ou classe), comme REPL va essayer de l'imprimer, et il n'utilise toString.