Création d'une mémoire O (1) Iterable à partir d'un objet initial et d'une fonction générant l'objet suivant, en Scala

Question

Je souhaite un moyen pratique de générer un objet Iterable, en lui affectant un objet initial et une fonction pour produire l'objet suivant celui qui consomme la mémoire O (1) (c.-à-d., il ne cache pas les anciens résultats, si vous voulez répéter une seconde fois, la fonction doit être appliquée à nouveau).

Il semble qu'il n'y ait pas de support de bibliothèque pour cela. Dans Scala 2.8, la méthode scala.collection.Iterable.iterate a la signature

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

donc il faut que vous spécifiez le nombre d'applications de fonctions itérées 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 scala.collection.Iterator.iterate a la 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.

Existe-t-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 ce faire?

En résumé, étant donné un objet initial a: A, et une fonction f: A => A, je voudrais un TraversableLike (par exemple, probablement un Iterable) qui génère a, f(a), f(f(a)), ..., et utilise la mémoire de O (1), avec map, filter etc fonctions qui retournent aussi quelque chose qui est O (1) en 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)) } 
    } 
} 

(cela peut ne pas fonctionner 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 ce n'était pas fait en mémoire constante cela causerait une erreur de tas (puisque cela alloue quelque chose comme 900 * 10mb).

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

Answer 2

Stream va faire ce que vous voulez, ne vous attachez pas aux cellules; seulement itérer sur les valeurs.

C'est un malentendu tristement répandu qui circule autour de ce que Streams cache de manière inhérente chaque valeur 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 retenu, mais ce n'est pas nécessaire. Si vous écrivez:

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

et si l'appelant seulement itère sur les valeurs de flux, mais ne se souvient pas de la valeur de flux lui-même (en particulier l'une de ses cellules contre), aucune rétention indésirable se produit. Bien sûr, dans cette formulation, chaque appel crée un nouveau 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 surveiller est le passage d'un Stream à une méthode. Cela permettra de capturer la tête du flux transmis dans le paramètre de la méthode. Une solution consiste à traiter le flux avec du code récursif.

Answer 3

Iterator est exactement ce que vous voulez. Et itérateur do a map, filter, takeWhile et beaucoup d'autres méthodes qui est O (1) en mémoire. Je ne pense pas qu'il existe un autre type de collection avec O (1) en 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 pas toString.