haskell - 这段模糊的Haskell代码如何工作？

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

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

当我在ghci中运行该代码段(在导入Data.Function和Control.Applicative之后)时，ghci显示2的所有幂的列表。

此段代码如何工作？

最佳答案

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

x = 1 : map (2*) x

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

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)