93

https://en.uncyclopedia.co/wiki/Haskellを読んでいるときに (そしてすべての「攻撃的な」ものを無視して)、次の難読化されたコードに出くわしました。

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

そのコードをghci(インポートした後Data.Function)Control.Applicativeで実行するとghci、2 のすべての累乗のリストが出力されます。

このコードはどのように機能しますか?

4

3 に答える 3

222

まず、素敵な定義があります

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)

これで、その定数の 2 つのコピーができました1。これではうまくいかないので、reader applicative を使用して重複を排除します。あと、関数合成がちょっとゴミっぽいので、そこそこ置き換えてみましょう(<$>)。

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

次は、 への呼び出しmapがあまりにも読みにくいです。しかし、恐れることは何もありません: モナド法則を使って少し拡張することができます。特に 、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)
于 2012-09-30T10:26:44.540 に答える
15

最終的なコードに至るまでの実験の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ました$1。「マップを不必要に複雑にする」ステップは（その初期には）起こりませんでした。
  • liftA2の代わりにliftM2を使用しました
  • 難読化mapされた機能は、liftM2をApplicativeコンビネータに置き換える前に導入されました。それはまた、すべてのスペースが消えたときです。
  • 私の「最終」バージョンでさえ、.関数合成のためにたくさん残っていました。それらすべてを、それと<$>アンサイクロペディアの間の数ヶ月のある時期に起こったようです。

ところで、これはもはや番号について言及していない更新されたバージョンです2：

fix$(<$>)<$>(:)<*>((<$>((:[{- Jörð -}])<$>))(=<<)<$>(*)<$>(>>=)(+)($))$1
于 2013-02-09T01:03:49.143 に答える