Полный список производящих чисел Фибоначчи, которые вписываются в инт


Я продвигаюсь через проблем, перечисленных в projecteuler.com как я узнаю Скала (мой блог, где я пишу о этом опыте). Я написал функцию для получения всех чисел Фибоначчи можно в инт (всего 47). Однако, результирующая функция чувствует императив (не функциональные).

  val fibsAll = {
    //generate all 47 for an Int
    var fibs = 0 :: List()
    var current = fibs.head
    var next = 1
    var continue = true
    while (continue) {
      current = fibs.head
      fibs = next :: fibs
      continue = ((0.0 + next + current) <= Int.MaxValue)
      if (continue)
        next = next + current
    }
    fibs.reverse
  }

Я ищу отзывы на этот код:

  1. В какой степени наличие даже один ВАР (это четыре) указывают на ошибку, подход с функциональной точки зрения?
  2. Я хочу вернуть список[Инт], есть ли лучший способ, чтобы сделать это рекурсивно, в отличие от моей нынешней (нечетные) "петли" подход?

Я нахожу переход от императивного к функциональному мышления довольно сложно.



Комментарии
2 ответа

object Euler002 extends App{
// Infinite List (Stream) of Fibonacci numbers
def fib(a: Int = 0, b: Int = 1): Stream[Int] = Stream.cons(a, fib(b, a+b))

// Take how many numbers you want into a List
val fibsAll = fib() takeWhile {_>=0} toList
fibsAll reverse
}

Взгляните на это.

6
ответ дан 24 июля 2011 в 08:07 Источник Поделиться

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

Например:

var continue = true
while (continue) {

Так, дальше , это правда (по крайней мере в первый раз это выполняется). Могу ли я заменить, тогда, когда (продолжить) с пока (истина) и есть весь остальной код работает, как ожидалось? Ответ: Нет, конечно.

Однако, учтите, что этот код генерирует fibsAll который представляет собой список чисел Фибоначчи меньше, чем Инт.MaxInt. Если я заменю весь определение fibsAll с этим списком, буду дальше действовать, как ожидалось? Да, он будет!

Так что даже если вы потеряли референциальной прозрачности в небольшом, что ты сохранил ее в большом. Если вы должны пойти на компромисс на ФП, это своего рода компромисс вы должны стремиться.

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

import scala.annotation.tailrec // turns non-tail recursion into an error
val fibsAll = {
@tailrec def recurse(current: Int, next: Int, acc: List[Int]): List[Int] =
if (next >= current) recurse(next, next + current, current :: acc)
else acc
recurse(0, 1, Nil).reverse
}

Не хвост рекурсивной версии это проще, и, поскольку список довольно маленький, вам вряд ли удастся сделать ошибки переполнения стека.

val fibsAll = {
def recurse(current: Int, next: Int): List[Int] =
if (next >= current) current :: recurse(next, next + current)
else Nil
recurse(0, 1)
}

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

val fibsAll = (
Stream.iterate(0 -> 1){ case (a, b) => (b, a + b) }
takeWhile { case (a, b) => b >= a }
map { case (a, b) => a }
toList
)

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

val fibsAll = (0, 1).unfold[List, Int]{ 
case (a, b) =>
if (a > b) None
else Some(a -> (b, a + b))
}

6
ответ дан 25 июля 2011 в 07:07 Источник Поделиться