The Obfuscated Fibonacci; or, a Curious Connection in Computation

I want to share with you a implementation of the fibonacci sequence in Haskell:

fibs = let f a = sum a : f (a >>= ([[0,1], [0]] !!)) in f [0]

The remainder of this post is an explanation of this code (and some neat extras). If you want to treat it as a puzzle and figure out why it works, you should treat the rest of this post as a spoiler.

Let’s start at the beginning.

The Beginning

First, a word of warning: This blog post has no practical use whatsoever. It’s merely the result of some lunchtime muckings about with formal systems. Now that you are forewarned, I’ll continue.

Simply put, the code is a string rewriting system with two rules. To explain it, I’ll first give some background.

Here’s a very simple system with a single rule (α → αβ) and an initial string (α).

α → αβ
α

To “run” the system, apply the production rules in order to each character of the input string and concatenate the results. Applying the rules to the string α gives us αβ. Applying them to αβ gives αββ.

Repeated application of the rules starting with α gives the following sequence of strings:

α
αβ
αββ
αβββ
αββββ

It’s pretty easy to see that we’ll just be adding one β each time.

Adding a Rule

To make things more interesting, I’ve added one more production rule: β → α. I’ll keep the start string (α) the same. This system of two rules is exactly what the “obfuscated fibonacci” code at the beginning of the article is implementing.

Repeated application of the rules gives:

α → αβ
β → α

α
αβ
αβα
αβααβ
αβααβαβα
αβααβαβααβααβ
αβααβαβααβααβαβααβαβα

Before reading on, it might be nice to look at these strings and see what you can divine about them. I’ll be spoiling many things you can notice in the next section, where I notice some facts for you.

Noticing some Facts

Instead of telling you directly, I will outline my thought process when I first looked at these strings. I hope it entertains you:

Hey, all the βs line up! Those stems came in handy.

Wait, that means all the αs do too!

Wait, that means that every string is a prefix of the next string

Hey, every string is also a suffix of the string after next!

That means each string is the concatenation of the previous two.

That reminds me of something…

That “something” is of course the fibonacci numbers: the sequence formed where each number is the sum of the previous two. This made me curious, so I computed the lengths of each string in the sequence to get the following:

1, 2, 3, 5, 8, 13, 21

Which is of course, the fibonacci numbers less the initial 0 and 1.

There are many other interesting properties, too.

For example, the ratio of αs to βs converges to the golden ratio. The reason is more clear if you also note that the number of αs and βs in each string also form the fibonacci sequence, but at different “lags”:

# βs   : [0, 1, 1, 2, 3, 5 , 8 , 13, 21, 34, 55 ]
# αs   : [1, 1, 2, 3, 5, 8 , 13, 21, 34, 55, 89 ]
lengths: [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

In the fibonacci sequence, the ratio of consecutive terms \(\frac{F_n}{F_{n - 1}}\) converges to the the golden ratio \(\phi\) as \(n\) increases. Because the sequence βs is αs lagged by one, we’re computing the ratio of consecutive fibonacci numbers.

Note also that the number of αs and βs sum to the total length of the string, so it’s quite natural that they should both form the fibonacci sequence lagged by 1 and 2 places.

However, we could be wrong: what if each string isn’t the concatenation of the previous two? It could be a huge coincidence! We should prove to our satisfaction that this is indeed correct.

Proving A Fact to Our Satisfaction

We’ve specified that α is the first string, so we know that’s true by assumption. We can obtain the second and third strings, αβ and αβα by applying the rules by hand.

I’ll make the following notational definitions first:

By definition, \(f\) is the function to get the next string, so \(f(S_n) = S_{n + 1}\). We want to prove (for \(n > 1\)) that each string is a concatenation of the previous two, i.e.

\[S_n = S_{n - 1} + S_{n - 2}\]

By inspection:

\[ \begin{alignat}{2} S_0 &= \alpha \\ S_1 &= \alpha \beta \\ S_2 &= \alpha \beta \alpha \\ &= \alpha \beta + \alpha \\ &= S_1 + S_0 \end{alignat} \]

That is, \(S_n = S_{n - 1} + S_{n - 2}\) for \(n = 2\).

This serves as a base case for a proof by induction. Now we need to prove the inductive step for all strings \(S(n)\) for \(n > 2\).

\[ \begin{alignat}{2} S_n &= f(S_{n - 1}) \\ &= f(S_{n - 2} + S_{n - 3}) \\ &= f(S_{n - 2}) + f(S_{n - 3}) \\ &= S_{n - 1} + S_{n - 2} \end{alignat} \]

Note the assumption that \(f(x + y) = f(x) + f(y)\). This is true because of the definition of \(f\): it concatenates the expansion of each symbol in order. I won’t try to be rigorous in proving this, but hopefully you’re convinced!

The Fibonacci Connection

At this point it should be obvious why this system has some connection to the fibonacci sequence. The \(n^{th}\) fibonacci number is defined as

\[F_n = F_{n - 1} + F_{n - 2}\]

Which is identical to our equation:

\[S_n = S_{n - 1} + S_{n - 2}\]

The only difference being the meaning of the \(+\) operator.

Now we can simply observe that taking the length of any string \(S_n\) is the same as adding the length of the previous two. That is, if \(L(S_n)\) is the length of string \(n\), then

\[L(S_n) = L(S_{n - 1}) + L(S_{n - 2})\]

Where \(+\) here denotes addition of natural numbers.

Because the first two lengths are 1 and 2, the lengths of strings therefore form the fibonacci sequence.

Un-golfing

Now i’ll reveal the original, slightly clearer implementation of my obfuscated Fibonacci function:

-- Production rules. A map from a char to the string to replace it with.
rules :: [(Char, String)]
rules = [('a', "ab"), ('b', "a")]

-- Rewrite a string using some production rules
rewrite :: Eq a => [(a, [a])] -> [a] -> [a]
rewrite rules s = s >>= \c -> maybe [c] id (lookup c rules)

-- unfold an infinite list
unfold :: (a -> a) -> a -> [a]
unfold f a = let a' = f a in a : unfold f a'

-- Print first 10 strings in the sequence with their lengths
main :: IO ()
main = mapM_ printWithLen . take 10 . unfold (rewrite rules) $ "a"
  where printWithLen s = putStr ((++ "\t") . show $ length s) >> putStrLn s

This code should hopefully be quite readable, but here’s a breakdown:

• rewrite takes a string, and applies the given rewrite rules to each character, and concatenates the results
• unfold repeatedly applies a function to an initial seed, yielding an infinite list
• main is the combination of these, applying “rewrite rules” to an initial string “a”, to give an infinite list of strings.

To compress this down into the original code (below), I made the following changes:

fibs = let f a = sum a : f (a >>= ([[0,1], [0]] !!)) in f [0]

1. Merge the functions “unfold” and “rewrite”
2. Switch from Char symbols to Int, with α as 0 and β as 1.
3. Lookup rules by position instead of by symbol
4. Hard-code the rewrite rules ([[0,1], [0]]) and initial string ([0])
5. Replace each rewritten string with its sum

Point 3 means that rewriting the symbol 0 can be done simply by replacing it with whatever’s in position 0 of the list of rules. That means using the list index function (!!). In the “clean” code, that might have looked like this:

rules :: [[Int]]
rules = [[0, 1], [0]]

rewrite :: [[Int]] -> [Int] -> [Int]
rewrite rules s = s >>= (rules !!)

Finally, instead of yielding a list of strings, I’ve summed each list of ints. This is to count the number of βs, which as we know from earlier, also forms the fibonacci sequence.

Further Reading

As it turns out, this kind of system is known as an “L-System”, invented by Aristid Lindenmayer as a model of plant growth.

In particular, the system of two rules I described is an L-System called “Algae”. You can read more about it on Wikipedia

There are a couple fun facts that didn’t really fit into the main article. If you are still interested, feel free to read on!

Neat Extras

We have two very similar equations:

The concatenation of two strings to form the next:

\[S_n = S_{n - 1} + S_{n - 2}\]

and the addition of two numbers to form the next:

\[F_n = F_{n - 1} + F_{n - 2}\]

In general, we’re forming a sequence from two initial values of some type and a binary operation on values of that type. This rings monoid-shaped bells in my mind, although really we only need a Magma: A set (or type) and a single binary operation on values of that set.

An interesting question is then: what does the fibonacci sequence look like under different sets (types) and operations? Let’s first implement “generalised fibs” in Haskell:

-- | Fibs generalised to any type and binary operation
gfibs :: (a -> a -> a) -> a -> a -> [a] 
gfibs f a b = a : gfibs f b (f b a)

Now a few examples:

-- | Regular 'ole fibonacci numbers with Integers and addition
fibs     = gfibs (+) 0 1

-- | Fibs with integers and product
-- take 10 pfibs == [1,2,2,4,8,32,256,8192,2097152,17179869184]
pfibs    = gfibs (*) 1 2

-- | Fibs with strings and concatenation (the "algae" system)
-- take 5 sfibs == ["a","ab","aba","abaab","abaababa"]
sfibs    = gfibs (++) "a" "ab"

pfibs is particularly interesting: its \(n^{th}\) term is equal to \(2^{F_n}\). That’s because the recurrence relation is written as the following:

\[ P_n = P_{n - 1} \cdot P_{n - 2} \]

Because \(P_1 = 2\) and \(P_2 = 2\), we have

\[ \begin{alignat}{2} P_3 &= 2^1 \cdot 2^1 \\ &= 2^{1 + 1} \\ &= 2^{F_3} \end{alignat} \]

And so in general,

\[ \begin{alignat}{2} P_n &= 2^{F_{n-1}} \cdot 2^{F_{n-2}} \\ &= 2^{F_{n-1} + F_{n-2}} \\ &= 2^{F_n} \end{alignat} \]

This works for other numbers too. If we’d written

pfibs = gfibs (*) 1 3

We would find that \(P_n = 3^{F_n}\).