Bagaimana cara kerja kode Haskell yang dikaburkan ini?

Saat membaca https://en.uncyclopedia.co/wiki/Haskell (dan mengabaikan semua hal "ofensif"), saya menemukan potongan kode berikut yang dikaburkan:

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

Ketika saya menjalankan bagian kode itu di ghci(setelah mengimpor Data.Functiondan Control.Applicative), ghcimencetak daftar semua pangkat 2.

Bagaimana cara kerja kode ini?

Pertama-tama, kami memiliki definisi yang indah

x = 1 : map (2*) x

yang dengan sendirinya agak membingungkan jika Anda belum pernah melihatnya sebelumnya. Pokoknya itu trik kemalasan dan rekursi yang cukup standar. Sekarang, kita akan menghilangkan penggunaan rekursi eksplisit fix, dan point-free-ify.

x = fix (\vs -> 1 : map (2*) vs)
x = fix ((1:) . map (2*))

Hal berikutnya yang akan kita lakukan adalah memperluas :bagian tersebut dan menjadikannya maprumit yang tidak perlu.

x = fix ((:) 1 . (map . (*) . (*2)) 1)

Nah, sekarang kita memiliki dua salinan dari konstanta itu 1. Itu tidak akan pernah berhasil, jadi kami akan menggunakan aplikasi pembaca untuk menghilangkan duplikatnya. Selain itu, komposisi fungsi agak sedikit sampah, jadi mari kita ganti dengan apa (<$>)pun yang kita bisa.

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

Selanjutnya: panggilan ke mapitu terlalu mudah dibaca. Tapi tidak ada yang perlu ditakuti: kita bisa menggunakan hukum monad untuk mengembangkannya sedikit. Secara khusus fmap f x = x >>= return . f, jadi

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

Kita dapat point-free-ify, menggantinya (.)dengan (<$>), dan kemudian menambahkan beberapa bagian palsu:

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

Mengganti persamaan ini di langkah sebelumnya:

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

Akhirnya, Anda mematahkan bilah spasi dan menghasilkan persamaan akhir yang indah

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

Sedang menulis jawaban panjang dengan menjalankan penuh log IRC saya dari percobaan yang mengarah ke kode akhir (ini di awal 2008), tapi saya tidak sengaja semua teks :) Meskipun tidak banyak kerugian - untuk sebagian besar analisis Daniel tepat.

Inilah yang saya mulai dengan:

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 *))

Perbedaannya sebagian besar turun ke urutan di mana refactoring terjadi.

• Alih-alih x = 1 : map (2*) xsaya mulai dengan 2 : map ..., dan saya menyimpan 2 awal itu sampai versi yang paling terakhir, di mana saya memasukkan a (*2)dan mengubahnya $2di bagian akhir menjadi $1. Langkah "buat peta menjadi sangat rumit" tidak terjadi (sedini itu).
• Saya menggunakan liftM2, bukan liftA2
• Fungsi obfuscated mapdimasukkan sebelum mengganti liftM2 dengan kombinator Aplikatif. Itu juga saat semua ruang menghilang.
• Bahkan versi "terakhir" saya memiliki banyak .komposisi fungsi yang tersisa. Mengganti semua itu dengan <$>tampaknya terjadi beberapa waktu di bulan-bulan antara itu dan uncyclopedia.

BTW, inilah versi terbaru yang tidak lagi menyebutkan nomor tersebut 2:

fix$(<$>)<$>(:)<*>((<$>((:[{- Jörð -}])<$>))(=<<)<$>(*)<$>(>>=)(+)($))$1

Kedua jawaban memperoleh potongan kode yang dikaburkan dari aslinya yang pendek yang diberikan secara tiba-tiba, tetapi pertanyaan sebenarnya menanyakan bagaimana kode yang telah lama dikaburkan melakukan tugasnya.

Begini caranya:

fix$(<$>)<$>(:)<*>((<$>((:[{- thor's mother -}])<$>))(=<<)<$>(*)<$>(*2))$1 
= {- add spaces, remove comment -}
fix $ (<$>) <$> (:) <*> ( (<$> ((:[]) <$>) ) (=<<)  <$>  (*)  <$>  (*2) ) $ 1 
--                      \__\______________/_____________________________/
= {-    A   <$> B   <*> C                          $ x   =   A (B x) (C x) -}
fix $ (<$>) (1 :)     ( ( (<$> ((:[]) <$>) ) (=<<)  <$>  (*)  <$>  (*2) ) 1 )
--                      \__\______________/____________________________/
= {- op f g = (f `op` g) ; (`op` g) f = (f `op` g) -}
fix $ (1 :) <$>  ( (((=<<) <$> ((:[]) <$>) )        <$>  (*)  <$>  (*2) ) 1 )
--                  \\____________________/____________________________/
= {- <$> is left associative anyway -}
fix $ (1 :) <$>  ( ( (=<<) <$> ((:[]) <$>)          <$>  (*)  <$>  (*2) ) 1 )
--                  \__________________________________________________/
= {- A <$> foo = A . foo when foo is a function -}
fix $ (1 :) <$>  ( ( (=<<) <$> ((:[]) <$>)           .   (*)   .   (*2) ) 1 )
--                  \__________________________________________________/
= {- ((:[]) <$>) = (<$>) (:[]) = fmap (:[])  is a function -}
fix $ (1 :) <$>  ( ( (=<<)  .  ((:[]) <$>)           .   (*)   .   (*2) ) 1 )
--                  \__________________________________________________/
= {- (a . b . c . d) x = a (b (c (d x))) -}
fix $ (1 :) <$>      (=<<)  (  ((:[]) <$>)           (   (*)   (   (*2)   1 )))
= {- (`op` y) x = (x `op` y) -}
fix $ (1 :) <$>      (=<<)  (  ((:[]) <$>)           (   (*)   2             ))
= {- op x = (x `op`) -}
fix $ (1 :) <$>      (=<<)  (  ((:[]) <$>)              (2*)                  )
= {-  (f `op`) g = (f `op` g) -}
fix $ (1 :) <$>      (=<<)  (   (:[]) <$>               (2*)                  )
= {-  A <$> foo = A . foo when foo is a function -}
fix $ (1 :) <$>      (=<<)  (   (:[])  .                (2*)                  )
= {-  (f . g) = (\ x -> f (g x)) -}
fix $ (1 :) <$>      (=<<)  (\ x -> [2*x]  )
= {- op f = (f `op`)  -}
fix $ (1 :) <$>           ( (\ x -> [2*x]  )  =<<)

Ini ( (\ x -> [2*x]) =<<) = (>>= (\ x -> [2*x])) = concatMap (\ x -> [2*x]) = map (2*)adalah fungsinya, jadi sekali lagi <$> = .,:

= 
fix $ (1 :)  .  map (2*)
= {- substitute the definition of fix -}
let xs = (1 :) . map (2*) $ xs in xs
=
let xs = 1 : [ 2*x | x <- xs] in xs
= {- xs = 1 : ys -}
let ys =     [ 2*x | x <- 1:ys] in 1:ys
= {- ys = 2 : zs -}
let zs =     [ 2*x | x <- 2:zs] in 1:2:zs
= {- zs = 4 : ws -}
let ws =     [ 2*x | x <- 4:ws] in 1:2:4:ws
=
iterate (2*) 1
= 
[2^n | n <- [0..]]

adalah semua pangkat 2 , dalam urutan yang meningkat.

Ini menggunakan

• A <$> B <*> C $ x = liftA2 A B C xdan karena liftA2 A B Cditerapkan xpadanya sebuah fungsi, an sebagai fungsi artinya liftA2 A B C x = A (B x) (C x).
• (f `op` g) = op f g = (f `op`) g = (`op` g) f adalah tiga hukum bagian operator

• >>=adalah ikatan monadik, dan sejak (`op` g) f = op f gdan jenisnya

  (>>=)                :: Monad m => m a -> (a -> m b ) -> m b
  (\ x -> [2*x])       :: Num t   =>         t -> [ t]
  (>>= (\ x -> [2*x])) :: Num t   => [ t]               -> [ t]
  

  berdasarkan jenis aplikasi dan substitusi kita melihat bahwa monad yang dimaksud adalah []untuk yang mana (>>= g) = concatMap g.

• concatMap (\ x -> [2*x]) xs disederhanakan sebagai

  concat $ map (\ x -> [2*x]) 
  =
  concat $ [ [2*x] | x <- xs]
  =
           [  2*x  | x <- xs]
  =
           map (\ x ->  2*x )
  

• dan menurut definisi,

  (f . g) x  =  f (g x)
  
  fix f  =  let x = f x in x
  
  iterate f x  =  x : iterate f (f x)
               =  x : let y = f x in 
                      y : iterate f (f y)
               =  x : let y = f x in 
                      y : let z = f y in 
                          z : iterate f (f z)
               = ...
               = [ (f^n) x | n <- [0..]]
  

  dimana

          f^n  =  f  .  f  .  ...  . f
          --     \_____n_times _______/
  

  yang seperti itu

  ((2*)^n) 1  =  ((2*) . (2*) .  ...  . (2*)) 1
              =    2*  (  2*  (  ...  (  2*   1 )...)) 
              =    2^n   ,  for n in [0..]