1. ホーム
  2. haskell

[解決済み] 難読化されたHaskellのコードはどのように動作するのでしょうか?

2023-02-22 14:21:20

質問

読書中 https://en.uncyclopedia.co/wiki/Haskell を読んでいるときに (そしてすべての不快なものを無視して)、次のような難読化されたコードの断片に出くわしました。

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

の中でこのコードを実行すると ghci (をインポートした後)。 Data.FunctionControl.Applicative ), ghci は2のすべての累乗のリストを表示します。

このコード片はどのように動作するのでしょうか?

どのように解決するのですか?

まず最初に、私たちは美しい定義を持っています。

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)

さて、この定数には2つのコピーがあります。 1 . これは決してうまくいかないので、リーダーアプリケーティブを使って重複をなくしましょう。また、関数の合成はちょっとくだらないので、次のように置き換えてみましょう。 (<$>) に置き換えましょう。

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)