tutorial - haskell用途




這段混淆的Haskell代碼是如何工作的? (2)

在閱讀http://uncyclopedia.wikia.com/wiki/Haskell (並忽略所有“冒犯性”的東西)時,我偶然發現了下面一段混淆的代碼:

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

當我在ghci運行這段代碼時(在導入Data.FunctionControl.Applicative ), ghci打印2的所有權力列表。

這段代碼是如何工作的?


我寫了一個很長的回答,其中包含了導致最終代碼的實驗的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,直到最後一個版本,我在(*2)擠壓並在$2處更改了$2最終變成$1 。 “製作地圖不必要的複雜”步驟沒有發生(那麼早)。
  • 我使用liftM2而不是liftA2
  • 在用適用的組合器替換liftM2之前,將模糊的map函數放入。 這也是所有空間消失的時候。
  • 即使我的“最終”版本也有很多. 剩下的功能組合。 用<$>代替所有這些顯然是在這段時間和非百科全書之間的幾個月裡發生的。

順便說一句,這是一個更新的版本,不再提及數字2

fix$(<$>)<$>(:)<*>((<$>((:[{- Jörð -}])<$>))(=<<)<$>(*)<$>(>>=)(+)($))$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 fx = x >>= return . f fmap fx = x >>= return . f ,所以

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

我們可以指出 - ify,用(<$>)替換(.) (<$>) ,然後添加一些虛假的部分:

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

在我們之前的步驟中替換這個公式:

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

最後,你打破你的空格,並產生美妙的最終方程

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






haskell