在Haskell中过滤fibonacci序列

Question

我正在尝试过滤包含斐波那契数字的列表.

我需要的只是奇数,而不是或等于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]

Answer 1

看看Data.List 中的takeWhile函数(并由Prelude重新导出).例如,

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

请注意,即使列表是无限的,一旦找到不满足谓词的元素,它就会终止.

Answer 2

还有一种更有效的方法来计算斐波纳契数:

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

可以过滤哪些只给出奇数:

oddFibs = filter odd fibs

哪个可以被截断为小于或等于N:

oddFibsLeN n = takeWhile (<= n) oddFibs