Суммирование значений в списке

Ответ 1

Здесь "стандартный" рекурсивный подход:

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
  }
}

И, здесь, функция хвоста-рекурсивная. Он будет более эффективен, чем функция, отличная от хвоста, поскольку компилятор превращает ее в цикл while, который не требует нажатия нового кадра в стеке для каждого рекурсивного вызова:

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)
}

Ответ 2

Также вы можете не использовать рекурсию напрямую и вместо этого использовать некоторые базовые абстракции:

val l = List(1, 3, 5, 11, -1, -3, -5)
l.foldLeft(0)(_ + _) // same as l.foldLeft(0)((a,b) => a + b)

foldLeft имеет значение reduce() в python. Также существует foldRight, который также известен как accumulate (например, в SICP).

Ответ 3

С рекурсией я часто считаю целесообразным подумать о том, как вы описываете процесс на английском языке, поскольку это часто переводится в код без особых усложнений. Так что...

"Как вычислить сумму списка целых чисел рекурсивно?"

"Ну, какая сумма списка, 3 :: restOfList?

" Что restOfList?

"Это может быть что угодно, вы не знаете. Но помните, мы рекурсивно - а разве у вас нет функции для вычисления суммы списка?"

"Ну ладно, тогда сумма будет 3 + sum(restOfList).

" Правильно. Но теперь ваша единственная проблема в том, что каждая сумма определяется в терминах другого вызова sum(), поэтому вы никогда не сможете получить фактическое значение. Вам понадобится какая-то база случай, когда все действительно достигнет, и что вы можете обеспечить значение для. "

" Хм, ты прав ". Думает...

" Ну, так как ваши списки становятся короче и короче, какой самый короткий список? "

" Пустой список? "

" Правильно! А какая сумма пустого списка int? "

" Zero - я получаю его сейчас, поэтому, суммируя его, сумма пустого списка равна нулю, а сумма любого другого списка - это его первый элемент, добавленный к сумме остальной части.

И действительно, код мог читать почти точно так же, как последнее предложение:

def sumList(xs: List[Int]) = {
    if (xs.isEmpty) 0
    else xs.head + sumList(xs.tail)
}

(Варианты соответствия шаблонов, такие как предложенные Ким Стебелем, по существу идентичны этому, они просто выражают условия более "функциональным" способом.)

Ответ 4

Вы не можете сделать это проще:

val list  = List(3, 4, 12);
println(list.sum); // result will be 19

Надеюсь, это поможет:)

Ответ 5

Ваш код хорош, но вам не нужно временное значение num. В Scala [If] - выражение и возвращает значение, это будет возвращено как значение функции sum. Поэтому ваш код будет реорганизован на:

def sum(xs: List[Int]): Int = {
    if(xs.isEmpty) 0
    else xs.head + sum(xs.tail)

}

Если список пуст, возвращаем 0, вы добавляете к главному номеру оставшуюся часть списка

Ответ 6

Каноническая реализация с сопоставлением с образцом:

def sum(xs:List[Int]) = xs match {
  case Nil => 0
  case x::xs => x + sum(xs)
}

Это не хвостовая рекурсия, но ее легко понять.

Ответ 7

В значительной степени основывается на ответе @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)
  }

Внутренняя функция рекурсивна, и когда предоставляется пустой список, вы получаете соответствующее исключение.

Ответ 8

 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)  
}

Ответ 9

Если вам требуется написать рекурсивную функцию с помощью isEmpty, head и tail, а также исключить исключение в случае аргумента пустого списка:

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)

Ответ 10

Чтобы добавить еще один возможный ответ на этот вопрос, вот решение, которое я придумал, это небольшая вариация ответа @jgaw и использует аннотацию @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)
}

Быстрая заметка о проверке наличия пустого списка; при программировании функционально предпочтительнее не бросать никаких исключений и вместо этого возвращать что-то другое (другое значение, функция, класс case и т.д.), чтобы обрабатывать ошибки элегантно и продолжать протекать через программирование, а не останавливать его с помощью Exception. Я бросил один в примере выше, так как мы просто смотрим на рекурсивно суммирующиеся элементы в списке.

Ответ 11

def sum(xs: List[Int]): Int = xs.sum

scala> sum(List(1,3,7,5))
res1: Int = 16

scala> sum(List())
res2: Int = 0

Ответ 12

Пробовал следующий метод без использования подстановочного подхода

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)
}