How does this piece of obfuscated Haskell code work?

Was writing a long answer with a full run-through of my IRC logs of the experiments leading up to the final code (this was in early 2008), but I accidentally all the text :) Not that much of a loss though - for the most part Daniel's analysis is spot on.

Here's what I started with:

Jan 25 23:47:23 <olsner>        @pl let q = 2 : map (2*) q in q
Jan 25 23:47:23 <lambdabot>     fix ((2 :) . map (2 *))

The differences mostly come down to the order in which the refactorings happened.

• Instead of x = 1 : map (2*) x I started with 2 : map ..., and I kept that initial 2 right up until the very last version, where I squeezed in a (*2) and changed the $2 at the end into $1. The "make the map needlessly complex" step didn't happen (that early).
• I used liftM2 instead of liftA2
• The obfuscated map function was put in before replacing liftM2 with Applicative combinators. That's also when all the spaces disappeared.
• Even my "final" version had lots of . for function composition left over. Replacing all of those with <$> apparently happened some time in the months between that and uncyclopedia.

BTW, here's an updated version that no longer mentions the number 2:

fix$(<$>)<$>(:)<*>((<$>((:[{- Jörð -}])<$>))(=<<)<$>(*)<$>(>>=)(+)($))$1

To begin with, we have the lovely definition

x = 1 : map (2*) x

which by itself is a bit mind-bending if you've never seen it before. Anyway it's a fairly standard trick of laziness and recursion. Now, we'll get rid of the explicit recursion using fix, and point-free-ify.

x = fix (\vs -> 1 : map (2*) vs)
x = fix ((1:) . map (2*))

The next thing we're going to do is expand the : section and make the map needlessly complex.

x = fix ((:) 1 . (map . (*) . (*2)) 1)

Well, now we have two copies of that constant 1. That will never do, so we'll use the reader applicative to de-duplicate that. Also, function composition is a bit rubbish, so let's replace that with (<$>) wherever we can.

x = fix (liftA2 (.) (:) (map . (*) . (*2)) 1)
x = fix (((.) <$> (:) <*> (map . (*) . (*2))) 1)
x = fix (((<$>) <$> (:) <*> (map <$> (*) <$> (*2))) 1)

Next up: that call to map is much too readable. But there's nothing to fear: we can use the monad laws to expand it a bit. In particular, fmap f x = x >>= return . f, so

map f x = x >>= return . f
map f x = ((:[]) <$> f) =<< x

We can point-free-ify, replace (.) with (<$>), and then add some spurious sections:

map = (=<<) . ((:[]) <$>)
map = (=<<) <$> ((:[]) <$>)
map = (<$> ((:[]) <$>)) (=<<)

Substituting this equation in our previous step:

x = fix (((<$>) <$> (:) <*> ((<$> ((:[]) <$>)) (=<<) <$> (*) <$> (*2))) 1)

Finally, you break your spacebar and produce the wonderful final equation

x=fix(((<$>)<$>(:)<*>((<$>((:[])<$>))(=<<)<$>(*)<$>(*2)))1)