这段模糊的Haskell代码如何工作?

问题描述 投票:88回答:2

[虽然阅读https://en.uncyclopedia.co/wiki/Haskell(并且忽略了所有“令人反感”的东西),但我偶然发现了以下混淆代码:

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

[当我在ghci中运行该代码段时(在导入Data.FunctionControl.Applicative之后,ghci打印2的所有幂的列表。

这段代码如何工作?

haskell
2个回答
213
投票

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

x = 1 : map (2*) x

如果您以前从未看过,那么这本身就有点令人费解。无论如何,这是懒惰和递归的相当标准的技巧。现在,我们将使用fix和无点自由化摆脱显式递归。

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

下一步,我们要做的是扩展:部分并使map变得不必要的复杂。

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

嗯,现在我们有了该常数1的两个副本。那永远不会做,所以我们将使用阅读器应用程序来消除重复。另外,函数的组成有点垃圾,因此我们尽可能地将其替换为(<$>)

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

下一步:调用map太容易理解了。但是没有什么可担心的:我们可以使用monad法则来对其进行扩展。特别是fmap f x = x >>= return . f,因此

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

我们可以进行无点修饰,用(.)替换(<$>),然后添加一些虚假部分:

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

在上一步中代入此等式:

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

最后,您打破了空格键并产生了精彩的最终方程式

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

14
投票

[我写了一个很长的答案,并完整地浏览了我的IRC日志,直到最终代码(这是在2008年初),但我无意中写了所有的内容:)在大多数情况下,Daniel的分析都在现场。

这是我的开始:

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个保留到最后一个版本,在那里我挤了一个(*2),最后将$2更改为$1。没那么早就发生了“使地图变得不必要的复杂”的步骤。
  • 我使用了liftM2而不是liftA2
  • 使用混淆组合器替换liftM2之前,加入了模糊的map功能。那也是所有空格都消失的时候。
  • 甚至我的“最终版本”也有很多.用于功能组合。用<$>代替所有这些化合物显然是在那和非百科全书之间的几个月中发生的。
  • BTW,这是更新的版本,不再提及数字2

fix$(<$>)<$>(:)<*>((<$>((:[{- Jörð -}])<$>))(=<<)<$>(*)<$>(>>=)(+)($))$1
© www.soinside.com 2019 - 2024. All rights reserved.