haskell - 这段混淆的 Haskell 代码是如何工作的？

Question

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

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

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

这段代码是如何工作的？

Answer 1

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

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)