Filtering fibonacci sequence in Haskell

2019-07-18 11:23发布

I'm trying to filter a list that contains the Fibonacci numbers.

What I need is only odd numbers, and less or equal than N.

This is what I have so far:

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]

That will give me what I want, but at the same time that solution won't work because I don't know how to stop retrieving elements from fib function. Of course, that is because of x <- [1..].

I have thought about two options:

  1. Placing a limit (that depends on n) in x <- [1..]
  2. Defining fibs recursive so I can know when to stop (thought about it while writing the question)

How could I do this?

I'm not looking for an efficient way

Edit:
Here are the two solutions I had at the end:

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 []

and the one using the suggestion of @hammar:

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

2条回答
Emotional °昔
2楼-- · 2019-07-18 12:02

There's also a more efficient way to compute Fibonacci numbers:

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

Which can be filtered to give only the odd numbers:

oddFibs = filter odd fibs

Which can be truncated to less than or equal to N:

oddFibsLeN n = takeWhile (<= n) oddFibs
查看更多
仙女界的扛把子
3楼-- · 2019-07-18 12:05

Have a look at the takeWhile function from Data.List (and re-exported by the Prelude). For example,

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

Note that even though the list is infinite, this terminates once it finds an element that does not satisfy the predicate.

查看更多
登录 后发表回答