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:
- Placing a limit (that depends on
n
) inx <- [1..]
- 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]
There's also a more efficient way to compute Fibonacci numbers:
Which can be filtered to give only the odd numbers:
Which can be truncated to less than or equal to N:
Have a look at the
takeWhile
function from Data.List (and re-exported by the Prelude). For example,Note that even though the list is infinite, this terminates once it finds an element that does not satisfy the predicate.