Предложите более чистый функциональный способ

Question

Вот некоторый императивный код:

var sum = 0
val spacing = 6
var x = spacing
for(i <- 1 to 10) {
  sum += x * x
  x += spacing
}

Вот две мои попытки «функционализировать» приведенный выше код:

// Attempt 1
(1 to 10).foldLeft((0, 6)) {
  case((sum, x), _) => (sum + x * x, x + spacing)
}

// Attempt 2
Stream.iterate ((0, 6)) { case (sum, x) => (sum + x * x, x + spacing) }.take(11).last

Я думаю, что может быть более чистый и функциональный способ сделать это. Что бы это было?

PS: Обратите внимание, что приведенный выше пример кода предназначен для иллюстрации проблемы; это не из реального кода приложения.

Answer 1

Заменив 10 на N, вы получите spacing * spacing * N * (N + 1) * (2 * N + 1) / 6

Это означает, что вы суммируете (интервал * i) ^ 2 для диапазона 1..N.Эта сумма разлагается как интервал ^ 2 * (1 ^ 2 + 2 ^ 2 + ... + N ^ 2), и последняя сумма, как известно, равна N * (N + 1) * (2 * N + 1)) / 6 (см. квадратное пирамидальное число )

Answer 2

Мне действительно нравится идея ленивых последовательностей в этом случае.Вы можете разбить свой алгоритм на 2 логических шага.

Сначала вы хотите работать со всеми натуральными числами (хорошо .. не все, но до макс. Целых), поэтому вы определяете их так:

val naturals = 0 to Int.MaxValue

Затем вам нужноопределить знания о том, как можно вычислить числа, которые вы хотите сложить:

val myDoubles = (naturals by 6 tail).view map (x => x * x)

И все это вместе:

val naturals = 0 to Int.MaxValue
val myDoubles = (naturals by 6 tail).view map (x => x * x)
val mySum = myDoubles take 10 sum

Я думаю, что математик подойдет к этой проблеме,И поскольку все коллекции лениво оцениваются - у вас не останется памяти.

Редактировать

Если вы хотите развить идею математической записи дальше, вы можете определить это неявное преобразование:

implicit def math[T, R](f: T => R) = new {
  def ∀(range: Traversable[T]) = range.view map f
}

и затем определите myDoubles следующим образом:

val myDoubles = ((x: Int) => x * x) ∀ (naturals by 6 tail)

Answer 3

Мой личный фаворит должен быть:

val x = (6 to 60 by 6) map {x => x*x} sum

Или задан spacing в качестве входной переменной:

val x = (spacing to 10*spacing by spacing) map {x => x*x} sum

или

val x = (1 to 10) map (spacing*) map {x => x*x} sum

Answer 4

Есть два разных направления. Если вы хотите выразить себя, предполагая, что вы не можете использовать встроенную функцию диапазона (потому что вы действительно хотите что-то более сложное):

Iterator.iterate(spacing)(x => x+spacing).take(10).map(x => x*x).foldLeft(0)(_ + _)

Это очень общий шаблон: укажите, с чего вы начинаете и как получить следующее с учетом предыдущего; затем возьмите необходимое вам количество предметов; затем преобразовать их как-нибудь; затем объедините их в один ответ. В простых случаях есть ярлыки для почти всех из них (например, последний раз - sum), но это способ сделать это вообще.

Но мне также интересно - что плохого в изменчивом императивном подходе к максимальной скорости? Это действительно довольно ясно, и Scala позволяет вам смешивать два стиля специально:

var x = spacing
val last = spacing*10
val sum = 0
while (x <= last) {
  sum += x*x
  x += spacing
}

(Обратите внимание, что for медленнее, чем while, поскольку компилятор Scala преобразует циклы for в конструкцию максимальной общности, а не максимальной скорости.)

Answer 5

Вот одна строка:

(0 to 10).reduceLeft((u,v)=>u + spacing*spacing*v*v)

Обратите внимание, что вам нужно начинать с 0, чтобы получить правильный результат (иначе будет добавлено только первое значение 6, но не в квадрате).

Другой вариант - сначала сгенерировать квадраты:

(1 to 2*10 by 2).scanLeft(0)(_+_).sum*spacing*spacing

Answer 6

Как насчет этого?

def toSquare(i: Int) = i * i
val spacing = 6
val spaceMultiples = (1 to 10) map (spacing *)
val squares = spaceMultiples map toSquare
println(squares.sum)

Вы должны разбить свой код на маленькие части.Это может значительно улучшить читаемость.

Answer 7

Вот прямой перевод цикла, который вы написали для хвостовой рекурсивной функции, в SML-подобном синтаксисе.

val spacing = 6
fun loop (sum: int, x: int, i: int): int =
  if i > 0 then loop (sum+x*x, x+spacing, i-1)
  else sum
val sum = loop (0, spacing, 10)

Это то, что вы искали?(Что вы подразумеваете под «чище» и «лучше»?)