Wie funktioniert dieser verschleierte Haskell-Code?

Beim Lesen von https://en.uncyclopedia.co/wiki/Haskell (und beim Ignorieren aller "anstößigen" Dinge) bin ich auf den folgenden verschleierten Code gestoßen:

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

Wenn ich diesen Code ausführe ghci(nach dem Importieren Data.Functionund Control.Applicative), wird ghcidie Liste aller Potenzen von 2 gedruckt.

Wie funktioniert dieser Code?

Zunächst haben wir die schöne Definition

x = 1 : map (2*) x

Das ist an sich schon ein bisschen umwerfend, wenn Sie es noch nie gesehen haben. Auf jeden Fall ist es ein ziemlich normaler Trick der Faulheit und Rekursion. Jetzt werden wir die explizite Rekursion mit fixund point-free-ify los.

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

Das nächste, was wir tun werden, ist den :Abschnitt zu erweitern und das mapunnötig komplex zu machen.

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

Nun haben wir zwei Kopien dieser Konstante 1. Das wird niemals funktionieren, also werden wir den Reader-Applikativ verwenden, um das zu duplizieren. Außerdem ist die Funktionszusammensetzung ein bisschen Unsinn. Ersetzen (<$>)wir sie also durch wo immer wir können.

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

Als nächstes: Dieser Aufruf von mapist viel zu lesbar. Aber es gibt nichts zu befürchten: Wir können die Monadengesetze verwenden, um sie ein wenig zu erweitern. Insbesondere fmap f x = x >>= return . falso

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

Wir können punktfrei ify, ersetzen (.)mit (<$>), und fügen Sie dann einige falsche Abschnitte:

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

Ersetzen Sie diese Gleichung in unserem vorherigen Schritt:

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

Schließlich brechen Sie Ihre Leertaste und erstellen die wunderbare endgültige Gleichung

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

Schrieb eine lange Antwort mit einem vollständigen Durchlauf meiner IRC-Protokolle der Experimente, die zum endgültigen Code führten (dies war Anfang 2008), aber ich habe versehentlich den gesamten Text :) Allerdings kein so großer Verlust - für die Zum größten Teil ist Daniels Analyse genau richtig.

Folgendes habe ich begonnen:

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

Die Unterschiede sind hauptsächlich auf die Reihenfolge zurückzuführen, in der die Refactorings durchgeführt wurden.

• Stattdessen habe x = 1 : map (2*) xich mit angefangen 2 : map ...und die ersten 2 bis zur letzten Version beibehalten, wo ich eine eingedrückt (*2)und die $2am Ende in geändert habe $1. Der Schritt "Karte unnötig komplex machen" fand nicht statt (so früh).
• Ich habe liftM2 anstelle von liftA2 verwendet
• Die verschleierte mapFunktion wurde aktiviert, bevor liftM2 durch anwendbare Kombinatoren ersetzt wurde. Dann verschwanden auch alle Räume.
• Sogar meine "endgültige" Version hatte viel .für die Funktionskomposition übrig. Das Ersetzen all dieser durch <$>anscheinend erfolgte einige Zeit in den Monaten zwischen dieser und der Unzyklopädie.

Übrigens, hier ist eine aktualisierte Version, in der die Nummer nicht mehr erwähnt wird 2:

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

Beide Antworten leiten das verschleierte Code-Snippet aus dem aus heiterem Himmel gegebenen kurzen Original ab, aber die Frage fragt tatsächlich, wie der lange verschleierte Code seine Aufgabe erfüllt.

Hier ist wie:

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]  )  =<<)

Hier ( (\ x -> [2*x]) =<<) = (>>= (\ x -> [2*x])) = concatMap (\ x -> [2*x]) = map (2*)ist eine Funktion, also noch einmal <$> = .:

= 
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..]]

sind alle Potenzen von 2 in aufsteigender Reihenfolge.

Dies verwendet

• A <$> B <*> C $ x = liftA2 A B C xund da es auf eine Funktion liftA2 A B Cangewendet wird, bedeutet xes als Funktion liftA2 A B C x = A (B x) (C x).
• (f `op` g) = op f g = (f `op`) g = (`op` g) f sind die drei Gesetze der Betreiberabschnitte

• >>=ist monadisch binden, und da (`op` g) f = op f gund die Typen sind

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

  Durch Typanwendung und Substitution sehen wir, dass die fragliche Monade []für welche ist (>>= g) = concatMap g.

• concatMap (\ x -> [2*x]) xs wird vereinfacht als

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

• und per Definition,

  (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..]]

  wo

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

  damit

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