# Fibonacci word check

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

## Leave a Comment