Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Filtering fibonacci sequence in Haskell

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]
like image 862
Oscar Mederos Avatar asked Apr 30 '26 19:04

Oscar Mederos


1 Answers

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.

like image 112
hammar Avatar answered May 03 '26 21:05

hammar



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!