Фильтрация последовательности Фибоначчи в Хаскеле - PullRequest
Новая
       12

Фильтрация последовательности Фибоначчи в Хаскеле

2 голосов
/ 04 мая 2011

Я пытаюсь отфильтровать список, содержащий числа Фибоначчи.

Мне нужны только нечетные числа, которые меньше или равны N.

Это то, что ядо сих пор: 

fib   n | n == 0         = 0
        | n == 1         = 1
        | otherwise = fib (n-1) + fib (n-2)

fibs n = [a | a <- [fib x | x <- [1..]], odd a, a < n]

Это даст мне то, что я хочу, но в то же время это решение не будет работать, потому что я не знаю как остановить извлечение элементов из функции fib.Конечно, это из-за x <- [1..].

Я думал о двух вариантах:

  1. Установка предела (который зависит от n) в x <- [1..]
  2. Определение fibs рекурсивного, чтобы я мог знать, когда остановиться (подумал об этом при написании вопроса)

Как я мог это сделать?

Я не ищу эффективный способ

Редактировать:
Вот два решения, которые у меня были в конце: 

fib   n | n == 0         = 0
        | n == 1         = 1
        | otherwise = fib (n-1) + fib (n-2)

fibsAux n k xs  | a < n     = fibsAux n (k+1) (xs ++ [a])
                | otherwise = xs
                where 
                    a = fib k
fibs n = filter odd $ fibsAux n 0 []

иодин, используя предложение @hammar: 

fibs x = takeWhile (< x) [a | a <- [fib x | x <- [1..]], odd n]

Ответы [ 2 ]

6 голосов
/ 04 мая 2011

Существует также более эффективный способ вычисления чисел Фибоначчи: 

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

, который можно отфильтровать, чтобы получить только нечетные числа: 

oddFibs = filter odd fibs

, который может быть усечен до менее чемили равно N: 

oddFibsLeN n = takeWhile (<= n) oddFibs
6 голосов
/ 04 мая 2011

Взгляните на функцию takeWhile из Data.List (и реэкспортированы с помощью Prelude).Например, 

takeWhile (< 4) [1..] == [1, 2, 3]

Обратите внимание, что, хотя список бесконечен, он завершается, когда находит элемент, который не удовлетворяет предикату.

...