para - ¿Cómo funciona este pedazo de código Haskell ofuscado?

ofuscar codigo wordpress

Question

Mientras leía http://uncyclopedia.wikia.com/wiki/Haskell (y haciendo caso omiso de todas las cosas "ofensivas"), me encontré con la siguiente pieza de código ofuscado:

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

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

¿Cómo funciona este código?

Answer 1

Estaba escribiendo una respuesta larga con un repaso completo de mis registros de IRC de los experimentos previos al código final (esto fue a principios de 2008), pero accidentalmente todo el texto :) No es una pérdida tan grande - para el la mayor parte del análisis de Daniel es perfecto.

Esto es lo que comencé 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 que ocurrieron las refactorizaciones.

• En lugar de x = 1 : map (2*) x comencé con 2 : map ... , y mantuve ese 2 inicial hasta la última versión, donde compré un (*2) y cambié los $2 en el final en $1 . El paso "hacer que el mapa sea innecesariamente complejo" no sucedió (tan temprano).
• Utilicé liftM2 en lugar de liftA2
• La función de map ofuscado se colocó antes de reemplazar liftM2 con combinators Applicative. Eso es también cuando todos los espacios desaparecieron.
• Incluso mi versión "final" tenía muchas . para la composición de la función sobrante. Reemplazando a todos aquellos con <$> aparentemente pasó algún tiempo 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

Answer 2

Para empezar, tenemos la encantadora definición

x = 1 : map (2*) x

que por sí solo 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 recursión 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 que el map innecesariamente complejo.

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

Bueno, ahora tenemos dos copias de esa constante 1 . Eso nunca funcionará, por lo que utilizaremos el lector aplicativo para quitar la duplicación. Además, la composición de la función es un poco basura, así que vamos a reemplazar eso con (<$>) siempre que podamos.

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

Siguiente: esa llamada al map es demasiado legible. Pero no hay nada que temer: podemos usar las leyes de mónada para expandirlo un poco. En particular, fmap fx = x >>= return . f fmap fx = x >>= return . f , entonces

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

Podemos señalar-free-ify, reemplazar (.) Con (<$>) y luego agregar algunas secciones falsas:

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)