How to find out if a number is in the Fibonacci Sequence

Question

I have created a function that gives the Fibonacci number for a given input. I now want to create a function to check if a given number is in the Fibonacci Sequence.

Here is what I have done so far:

-- Basic Fib Function 
fib :: Int -> Int 
fib x =
  if x < 1
    then 0
    else if x < 2
           then 1
           else fib (x - 1) + fib (x - 2)

-- Outputs list of all the functions 
fibList :: [Int]
fibList  = map fib [1..]
--  function that takes an Integer, and returns True if the argument is a Fibonacci number and False otherwise
isFib :: Int -> [Int] -> Bool
isFib n fibList
    |n `elem` fibList = True
    |otherwise = False

fibList works but the computation is taking very long time. Also, I have done this:

fibList' :: [Int]
fibList'  = map fib [1..100]

isFib' :: Int -> [Int] -> Bool
isFib' n fibList'
    |n `elem` fibList' = True
    |otherwise = False

With a smaller number, it still takes a long time to compute

ghci

Answer 1

The problem is that n is an Int and fibList is an [Int], you can not check if an Int and [Int] are the same, since these have a different type.

Using elem will also fail in case the given number is not a Fibonacci number, since Haskell will keep enumerating over the list looking for the next candidate and will only return False if it reaches the end of the list, but if you generate an infinite list, then this will never end.

You can implement the isFib function where we check if the first item of the list is greater than n. If that is the case, we know that all remaining elements will be larger, and thus we can stop searching:

isFib :: Int -> [Int] -> Bool
isFib _ [] = False
isFib n (x:xs)
    | x >= n = -- ...  🖘 to implement
    | otherwise = isFib n xs

where I leave filling in the … part as an exercise.

Your fib function is not very efficient: it will take exponential time to determine the n-th element. You can generate the Fibonacci numbers through recursion and check if one of the items we generate is indeed a Fibonacci number:

isFib :: Int -> Bool
isFib n = go 0 1
  where go f1 f2
          | f1 >= n = …
          | otherwise = go f2 (f1 + f2)