这段混淆的Haskell代码是如何工作的?

在阅读http://uncyclopedia.wikia.com/wiki/Haskell (并忽略所有“冒犯性”的东西)的时候,我偶然发现了下面一段混淆的代码:

fix$(<$>)<$>(:)<*>((<$>((:[{- thor's mother -}])<$>))(=<<)<$>(*)<$>(*2))$1 

当我在ghci运行这段代码时(在导入Data.FunctionControl.Applicative ), ghci打印2的所有权力列表。

这段代码是如何工作的?

首先,我们有一个可爱的定义

 x = 1 : map (2*) x 

如果你以前从来没有见过它,这本身就是一个让人挠头的地方。 无论如何,这是一个懒惰和recursion相当标准的伎俩。 现在,我们将摆脱显式recursion使用fix ,并免费。

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

接下来我们要做的是扩大:部分,使map不必要的复杂。

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

那么,现在我们有两个常数1副本。 这将永远不会做,所以我们将使用读者应用去重复。 另外,函数组合有点垃圾,所以我们尽可能地用(<$>)replace它。

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

接下来:那个调用map太可读了。 但是没有什么可怕的,我们可以用monad法来扩大一点。 特别是, fmap fx = x >>= return . f fmap fx = x >>= return . f ,所以

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

我们可以指出,用(<$>)replace(.) (<$>) ,然后添加一些虚假的部分:

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

在我们之前的步骤中代入这个等式:

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

最后,你打破你的空格,并产生了美好的最终方程

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

写了一个很长的答案,我的IRC日志的实验导致了最终的代码(这是在2008年初),但我不小心全部文本的完整运行:)虽然没有那么多的损失 – 对于丹尼尔的分析大部分都是现货。

这是我开始的:

 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 *)) 

差异主要归结为重构发生的顺序。

  • 而不是x = 1 : map (2*) x我从2 : map ...开始2 : map ... ,并且保留了最初的2,直到最后一个版本,我挤压了一个(*2)并且改变了$2最终变成$1 。 “制作地图不必要的复杂”一步没有发生(那早)。
  • 我使用liftM2而不是liftA2
  • 在用适用的组合器代替liftM2之前,将混淆的map函数放入。 所有的空间都消失了。
  • 即使我的“最后”版本也有很多. 剩余的function组合。 用<$>代替所有这些显然是在这个和那个百科全书之间的几个月里发生的。

顺便说一句,这是一个更新的版本,不再提及数字2

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