¿Cómo funciona esta pieza de código Haskell ofuscado?

Mientras leía https://en.uncyclopedia.co/wiki/Haskell (e ignorando todas las cosas "ofensivas"), me encontré con el siguiente código ofuscado:

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

Cuando ejecuto ese fragmento de código ghci(después de importar Data.Functiony Control.Applicative), ghciimprime la lista de todas las potencias de 2.

¿Cómo funciona este código?

Para empezar, tenemos la hermosa definición

x = 1 : map (2*) x

que en sí mismo es un poco alucinante si nunca lo has visto antes. De todos modos, es un truco bastante estándar de pereza y recursividad. Ahora, nos desharemos de la recursividad explícita usando fix, y point-free-ify.

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

Lo siguiente que vamos a hacer es expandir la :sección y hacer mapinnecesariamente complejo.

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

Bueno, ahora tenemos dos copias de esa constante 1. Eso nunca funcionará, así que usaremos el aplicativo del lector para eliminarlo. Además, la composición de funciones es un poco basura, así que reemplacemos eso con (<$>)lo que podamos.

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

A continuación: esa llamada a mapes demasiado legible. Pero no hay nada que temer: podemos usar las leyes de las mónadas para expandirlo un poco. En particular fmap f x = x >>= return . f, entonces

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

Podemos señalar, sin ify, sustituir (.)con (<$>), y luego añadir algunas secciones espurias:

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

Sustituyendo esta ecuación en nuestro paso anterior:

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

Finalmente, rompes tu barra espaciadora y produces la maravillosa ecuación final

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

Estaba escribiendo una respuesta larga con un repaso completo de mis registros de IRC de los experimentos que condujeron al código final (esto fue a principios de 2008), pero accidentalmente todo el texto :) Sin embargo, no es una gran pérdida, para el la mayor parte del análisis de Daniel es acertado.

Esto es lo que empecé con:

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

Las diferencias se reducen principalmente al orden en el que ocurrieron las refactorizaciones.

• En lugar de x = 1 : map (2*) xcomenzar con 2 : map ..., mantuve ese 2 inicial hasta la última versión, donde apreté a (*2)y cambié el $2al final por $1. El paso de "hacer el mapa innecesariamente complejo" no sucedió (tan pronto).
• Usé liftM2 en lugar de liftA2
• La mapfunción ofuscada se instaló antes de reemplazar liftM2 con combinadores aplicativos. Ahí fue también cuando todos los espacios desaparecieron.
• Incluso a mi versión "final" le sobró mucha .composición de funciones. Reemplazar todos aquellos con <$>aparentemente sucedió en algún momento en los meses entre eso y la inciclopedia.

Por cierto, aquí hay una versión actualizada que ya no menciona el número 2:

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

Ambas respuestas derivan el fragmento de código ofuscado del original corto dado de la nada, pero la pregunta en realidad pregunta cómo hace su trabajo el código largo y ofuscado.

Así es cómo:

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

Aquí ( (\ x -> [2*x]) =<<) = (>>= (\ x -> [2*x])) = concatMap (\ x -> [2*x]) = map (2*)hay una función, así que de nuevo <$> = .:

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

son todas las potencias de 2 , en orden creciente.

Esto usa

• A <$> B <*> C $ x = liftA2 A B C xy dado que liftA2 A B Cse aplica a xsu función, significa una función liftA2 A B C x = A (B x) (C x).
• (f `op` g) = op f g = (f `op`) g = (`op` g) f son las tres leyes de las secciones del operador

• >>=es unión monádica, y dado que (`op` g) f = op f gy los tipos son

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

  por tipo de aplicación y sustitución vemos que la mónada en cuestión es []para cuál (>>= g) = concatMap g.

• concatMap (\ x -> [2*x]) xs se simplifica como

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

• y por definición,

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

  dónde

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

  así que eso

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