итерационная функция не сохраняет промежуточные шаги?

Question

Я только начал изучать Haskell, и в качестве упражнения попал в задачу Project Euler, где суммируются числа Фибоначчи. Мой текущий метод - эта функция, которая создает новый список со следующим элементом:

fib :: (Integral a) => [a] -> [a]
fib xs@(x1:x2:_) = (x1+x2) : xs

Я нашел функцию iterate, которая повторно применяет функцию к ее результату. Однако результатом является список списков [[2,1],[3,2,1],[5,3,2,1],..]. Какая альтернатива iterate когда меня не интересуют промежуточные результаты? Я хочу сделать takeWhile с условием последнего сгенерированного числа. Это неправильный способ думать об этом вообще?

(я видел лучшие / более короткие / изящные способы генерации последовательности Фибоначчи, поэтому я не очень хочу получать отзывы о функции fib - но я бы хотел, чтобы она работала, неоптимальный метод или нет )

Answer 1

Просто используйте iterate!Поскольку Haskell является чистым языком, все подсписки становятся общими, и вы практически не платите за создание всех этих мини-списков: [2, 1] на самом деле 2, 1 в [3, 2, 1] и т. Д.

Вы на самом деле не хотите takeWhile, потому что это даст вам много лишнего мусора, и вам все равно придется добраться до конца списка с помощью last.Вместо этого используйте find.

Также обратите внимание, что если вы планируете суммировать итоговый список, вы пропустили 1, так что вы будете единичным.

Answer 2

Когда вам нужна функция в Haskell, просто определите ее:)

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

apply_n f n x =
    if n = 0 then x
    else apply_n' f (n-1) (f x)

n_th_fib n = apply_n fib n [1,1]

Я почти уверен, что есть более удобный способ сделать это, используя складки (или функцию библиотеки, о которой я забыл :))

Answer 3

Я бы использовал «взять», поскольку каждое последующее приближение будет на одно целое число более точным, чем последнее. Затем вы можете сделать (напр. Обратное) на это.

Обратите внимание, что "каждый" результат является промежуточным результатом, если итерируемая функция не имеет вычислимой фиксированной точки.

Answer 4

Я не уверен насчет использования iterate, но см. Фильтрация последовательности Фибоначчи в Haskell , чтобы узнать, как отфильтровать список выдумок.

Это то же домашнее задание