scala - resueltos - Sumando valores en una lista
mendenhall probabilidad y estadistica pdf (12)
Estoy intentando escribir una función de escala que sumará recursivamente los valores en una lista. Aquí está lo que tengo hasta ahora:
def sum(xs: List[Int]): Int = {
val num = List(xs.head)
if(!xs.isEmpty) {
sum(xs.tail)
}
0
}
No sé cómo sumar los valores Int individuales como parte de la función. Estoy considerando la posibilidad de definir una nueva función dentro de la suma de la función y estoy usando una variable local que suma valores a medida que la Lista se está repitiendo en iteración. Pero esto parece un enfoque imperativo. ¿Hay un método alternativo?
Aquí está el enfoque recursivo "estándar":
def sum(xs: List[Int]): Int = {
xs match {
case x :: tail => x + sum(tail) // if there is an element, add it to the sum of the tail
case Nil => 0 // if there are no elements, then the sum is 0
}
}
Y, aquí hay una función recursiva de cola. Será más eficiente que una función no recursiva de cola porque el compilador lo convierte en un bucle while que no requiere empujar un nuevo marco en la pila para cada llamada recursiva:
def sum(xs: List[Int]): Int = {
@tailrec
def inner(xs: List[Int], accum: Int): Int = {
xs match {
case x :: tail => inner(tail, accum + x)
case Nil => accum
}
}
inner(xs, 0)
}
Basándonos en la respuesta de @Kim:
def sum(xs: List[Int]): Int = {
if (xs.isEmpty) throw new IllegalArgumentException("Empty list provided for sum operation")
def inner(xs: List[Int]): Int = {
xs match {
case Nil => 0
case x :: tail => xs.head + inner(xs.tail)
}
}
return inner(xs)
}
La función interna es recursiva y cuando se proporciona una lista vacía, se genera la excepción apropiada.
Con la recursión, a menudo encuentro que vale la pena pensar cómo describiría el proceso en inglés, ya que eso a menudo se traduce en código sin demasiada complicación. Asi que...
"¿Cómo calculo recursivamente la suma de una lista de enteros?"
"Bueno, ¿cuál es la suma de una lista,
3 :: restOfList?"¿Qué es
restOfList?"Podría ser cualquier cosa, no lo sabes. Pero recuerda, estamos siendo recursivos, ¿y no tienes una función para calcular la suma de una lista?"
"¡Oh, cierto! Bueno, entonces la suma sería
3 + sum(restOfList)."Eso es correcto. Pero ahora su único problema es que cada suma se define en términos de otra llamada a
sum(), por lo que nunca podrá obtener un valor real. Necesitará algún tipo de caso básico que todo realmente alcanzará, y que puede proporcionar un valor para "."Hmm, tienes razón". Piensa ...
"Bueno, ya que sus listas son cada vez más cortas, ¿cuál es la lista más corta posible?"
"La lista vacía?"
"¡Cierto! ¿Y cuál es la suma de una lista vacía de entradas?"
"Cero: lo entiendo ahora. Entonces, al juntarlo, la suma de una lista vacía es cero, y la suma de cualquier otra lista es su primer elemento agregado a la suma del resto de la lista.
Y de hecho, el código podría leerse casi exactamente como la última frase:
def sumList(xs: List[Int]) = {
if (xs.isEmpty) 0
else xs.head + sumList(xs.tail)
}
(Las versiones de coincidencia de patrones, como la propuesta por Kim Stebel, son esencialmente idénticas a esto, solo expresan las condiciones de una manera más "funcional").
La implementación canónica con patrón de coincidencia:
def sum(xs:List[Int]) = xs match {
case Nil => 0
case x::xs => x + sum(xs)
}
Esto no es una cola recursiva, pero es fácil de entender.
No puedes hacerlo más fácil:
val list = List(3, 4, 12);
println(list.sum); // result will be 19
Espero eso ayude :)
Para agregar otra posible respuesta a esto, aquí hay una solución que se me ocurrió, que es una pequeña variación de la respuesta de @jgaw y usa la anotación @tailrec :
def sum(xs: List[Int]): Int = {
if (xs.isEmpty) throw new Exception // May want to tailor this to either some sort of case class or do something else
@tailrec
def go(l: List[Int], acc: Int): Int = {
if (l.tail == Nil) l.head + acc // If the current ''list'' (current element in xs) does not have a tail (no more elements after), then we reached the end of the list.
else go(l.tail, l.head + acc) // Iterate to the next, add on the current accumulation
}
go(xs, 0)
}
Nota rápida sobre los cheques para una lista vacía que se pasa; al programar funcionalmente, es preferible no lanzar excepciones y, en cambio, devolver otra cosa (otro valor, función, clase de caso, etc.) para manejar los errores con elegancia y seguir fluyendo a través de la programación en lugar de detenerlos mediante una Exception . Arrojé uno en el ejemplo anterior, ya que solo estamos viendo sumas recursivas en una lista.
Probé el siguiente método sin utilizar el método de sustitución.
def sum(xs: List[Int]) = {
val listSize = xs.size
def loop(a:Int,b:Int):Int={
if(a==0||xs.isEmpty)
b
else
loop(a-1,xs(a-1)+b)
}
loop(listSize,0)
}
Si debe escribir una función recursiva con isEmpty, head and tail, y también lanzar una excepción en el caso de un argumento de lista vacía:
def sum(xs: List[Int]): Int =
if (xs.isEmpty) throw new IllegalArgumentException("sum of empty list")
else if (xs.tail.isEmpty) xs.head
else xs.head + sum(xs.tail)
Su código es bueno pero no necesita el valor temporal num. En Scala [Si] es una expresión y devuelve un valor, se devolverá como el valor de la función de suma. Así tu código será refactorizado a:
def sum(xs: List[Int]): Int = {
if(xs.isEmpty) 0
else xs.head + sum(xs.tail)
}
Si la lista está vacía, devuelva 0; de lo contrario, agregue el número de cabecera al resto de la lista.
También puede evitar usar la recursión directamente y usar algunas abstracciones básicas en su lugar:
val l = List(1, 3, 5, 11, -1, -3, -5)
l.foldLeft(0)(_ + _) // same as l.foldLeft(0)((a,b) => a + b)
foldLeft es como reduce() en python. También existe foldRight que también se conoce como accumulate (por ejemplo, en SICP).
def sum(xs: List[Int]): Int = xs.sum
scala> sum(List(1,3,7,5))
res1: Int = 16
scala> sum(List())
res2: Int = 0
def sum(xs: List[Int]): Int = {
def loop(accum: Int, xs: List[Int]): Int = {
if (xs.isEmpty) accum
else loop(accum + xs.head, xs.tail)
}
loop(0,xs)
}