Continuar con la información sobre cómputos anteriores

Question

Soy nuevo en la programación funcional, por lo que algunos problemas parecen ser más difíciles de resolver con un enfoque funcional.

Digamos que tengo una lista de números, como 1 a 10.000, y quiero obtener los elementos de la lista que suman como máximo un número n (digamos 100). Entonces, obtendría los números hasta que su suma sea mayor que 100.

En la programación imperativa, es trivial resolver este problema, porque puedo mantener una variable en cada interacción y detenerme una vez que se alcanza el objetivo.

Pero, ¿cómo puedo hacer lo mismo en la programación funcional? Dado que la función de suma opera en listas completadas, y todavía no tengo la lista completa, ¿cómo puedo 'continuar' el cálculo?

Si suma se calculó con pereza, podría escribir algo así:

  (1 to 10000).sum.takeWhile(_ < 100) 

PS: A pesar de que será apreciado ninguna respuesta, me gustaría que no computa la suma cada vez, ya obviamente la versión imperativa será mucho más óptima con respecto a la velocidad.

Editar:

sé que puedo "convertir" el enfoque de bucle imprescindible para una función recursiva funcional. Estoy más interesado en encontrar si una de las funciones de biblioteca existentes puede proporcionarme una manera de no escribir una cada vez que necesite algo.

Answer 1

Use Stream.

scala> val ss = Stream.from(1).take(10000) 
ss: scala.collection.immutable.Stream[Int] = Stream(1, ?) 

scala> ss.scanLeft(0)(_ + _) 
res60: scala.collection.immutable.Stream[Int] = Stream(0, ?) 

scala> res60.takeWhile(_ < 100).last 
res61: Int = 91 

EDIT:

componentes Obtención no es muy difícil tampoco. Así es como puede hacerlo:

scala> ss.scanLeft((0, Vector.empty[Int])) { case ((sum, compo), cur) => (sum + cur, compo :+ cur) } 
res62: scala.collection.immutable.Stream[(Int, scala.collection.immutable.Vector[Int])] = Stream((0,Vector()), ?) 

scala> res62.takeWhile(_._1 < 100).last 
res63: (Int, scala.collection.immutable.Vector[Int]) = (91,Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)) 

La segunda parte de la tupla es el resultado deseado.

Como debería ser obvio, en este caso, construir un vector es un desperdicio. En cambio, solo podemos almacenar el último número de la secuencia que contribuyó a la suma.

scala> ss.scanLeft(0)(_ + _).zipWithIndex 
res64: scala.collection.immutable.Stream[(Int, Int)] = Stream((0,0), ?) 

scala> res64.takeWhile(_._1 < 100).last._2 
res65: Int = 13 

Answer 2

La forma en que haría esto es con recursion. En cada llamada, agregue el siguiente número. Su caso base es cuando la suma es mayor que 100, momento en el que regresa a la pila. Necesitarás una función de ayuda para hacer la recursión real, pero eso no es gran cosa.

Answer 3

Esto tampoco es difícil con los métodos "funcionales".
Al usar recursividad, en lugar de mantener su estado en una variable local que usted mute, lo mantiene en parámetros y valores devueltos.

Así que, volviendo a la parte inicial de una lista más larga cuya suma es a lo sumo N:

1. Si la lista está vacía, ya está hecho; devuelve la lista vacía
2. Si el encabezado de la lista es mayor que N, ya está; devuelve la lista vacía
3. De lo contrario, deje que H sea el primero de la lista.
   Todo lo que necesitamos ahora es la parte inicial de cola de la lista cuya suma es a lo sumo N - H, entonces podemos "contras" H en esa lista, y hemos terminado.
   Podemos calcular esto recursivamente utilizando el mismo procedimiento que hemos utilizado hasta ahora, por lo que es un paso fácil.

Una solución sencilla pseudocódigo:

sum_to (n, ls) = if isEmpty ls or n < (head ls) 
       then Nil 
       else (head ls) :: sum_to (n - head ls, tail ls) 

sum_to(100, some_list) 

Answer 4

Todas las operaciones de secuencias que requieren una sola pasada a través de la secuencia se pueden implementar utilizando pliegues nuestra reducen como se llama a veces. Me encuentro con pliegues muy a menudo desde que se convirtió utilizado para la programación funcional

así que aquí extraña un posible enfoque Usar una colección vacía como valor inicial y doblar de acuerdo con esta estrategia Dada la colección de procesado y el nuevo cheque valor si su suma es lo suficientemente baja y si luego gastar el valor en la colección else no hacer nada

esa solución no es muy eficiente pero quiero enfatizar el siguiente map fold filter zip etc. son la forma de acostumbrarse a la programación funcional try para utilizarlos tanto como sea posible en lugar de estructuras grotescas o funciones recursivas, su código será más declarativo y funcionará l