Fibonacci word check

less than 1 minute read




We define Fibonacci words as follows:
Check if a given word is a Fibonacci word in linear time. I'll give it a try in Haskell.

checkFibWord :: [Char] -> Bool
checkFibWord [] = False
checkFibWord xs = if (len==y) then aux xs ys else False where
len = length xs
(y:ys) = makeFibLenList len
aux "a" [] = True
aux "b" [] = True
aux "ba" [1,1] = True
aux zs (n1:n2:ns) = 
    ((take n2 zs) == (drop n1 zs)) && (aux (take n1 zs) (n2:ns))
aux _ _ = False

makeFibLenList :: Int -> [Int]
makeFibLenList len = aux 1 1 [] where
aux a b xs
| a >= len = (a:xs)
| otherwise = aux b (a+b) (a:xs)


makeFibWord :: Int -> [Char]
makeFibWord 0 = "a"
makeFibWord 1 = "b"
makeFibWord n = if (n<0) then "a" else aux 2 "ba" "b" n where
aux wnum w1 w0 num
| (wnum==num) = w1
| otherwise = aux (wnum+1) (w1++w0) w1 n


Updated:

Leave a Comment