Haskell- Find element in a list and return its position

Question

So i need to make a function described as

invFib :: Integer -> Maybe Integer

which takes an Integer and looks for it in the fibonacci sequence (as described by the function below)

fibs :: [Integer]
fibs = 0:1:(zipWith (+) fibs (tail fibs)) 

and returns the index of the number example:

invFib 0 ~> Just 0

invFib 1 ~> Just 1 or Just 2

map invFib [54, 55, 56] ~> [Nothing,Just 10,Nothing]

invFib (fibs !! 99) ~> Just 99

I tried making a function that takes a list of integers and spits out the index, but it keeps failing. Any thoughts?

this is function i tried-

findNum :: [Integer] -> Integer -> Integer -> Integer
findNum x:xs y z = if x == y
                then z
                else findNum xs y (z+1)

Edit: the function freezes on numbers not in the fibonacci sequence, also only shows 1 value when 1 is entered

invFib :: Integer -> Maybe Integer
invFib n = if n < 0
        then Nothing
        else fmap fromIntegral (elemIndex n fibs)

Answer 1

So the key here is that fibs is infinite, but also monotonically increasing. Hence, once it exceeds the number being looked for, it can return Nothing:

findIndexInAscendingList :: (Ord a) => a -> [a] -> Maybe Integer
findIndexInAscendingList a xs = find 0 xs
  where
    find i [] = Nothing -- won't get used for fibs
    find i (x:xs) | a == x    = Just i
                  | a < x     = Nothing
                  | otherwise = find (i + 1) xs

invFib :: Integer -> Maybe Integer
invFib n = findIndexInAscendingList n fibs

And so:

$ ghci
GHCi, version 7.4.2: http://www.haskell.org/ghc/  :? for help
λ: :load Fib.hs 
[1 of 1] Compiling Main             ( Fib.hs, interpreted )
Ok, modules loaded: Main.
λ: map invFib [54,55,56]
[Nothing,Just 10,Nothing]

There are some other ways to do it too. Think about zip fibs [0..] and then you could use dropWhile to remove the portion less than n and test what's left.

Answer 2

Why not use a function like 'takeWhile' to return a section of the infinite 'fibs' list that you want to examine? With the finite list, you could apply a function like 'elemIndex' which, with a little type adjustment, could return what you are after.

elemIndex myInteger (takeWhile (<= myInteger) fibs)

Answer 3

If you've already computed fibs, then the answer is simple:

import Data.List

invFib :: Integer -> Maybe Integer
invFib n = fmap fromIntegral (elemIndex n fibs)

fibs :: [Integer]
fibs = 0:1:(zipWith (+) fibs (tail fibs))