Comment fonctionne ce morceau de code obfusqué de Haskell ?

Question

Tout en http://uncyclopedia.wikia.com/wiki/Haskell de la lecture (et en ignorant tous les trucs « offensants »), je suis tombé sur le morceau de code obfusqué suivant :

Quand je lance ce morceau de code dans (après l’importation des et ), imprime la liste de toutes les puissances de 2.

Comment fonctionne ce morceau de code ?

Answer 1

Pour commencer, nous avons la belle définition

x = 1 : map (2*) x

ce qui en soi est un peu l'esprit de flexion si vous ne l'avez jamais vu avant. De toute façon c'est un assez truc standard de la paresse et de la récursivité. Maintenant, nous allons nous débarrasser de l'explicite en utilisant la récursivité fix, et le point-gratuit-identifier.

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

La prochaine chose que nous allons faire est de développer l' : section et de faire de l' map inutilement complexe.

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

Eh bien, maintenant nous avons deux copies de cette constante, 1. Que ne pourra jamais faire, nous allons utiliser le lecteur applicatif de le dupliquer. Aussi, en fonction de la composition est un peu de la foutaise, donc, nous allons la remplacer avec (<$>) partout où nous le pouvons.

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

Prochaine étape: que l'appel à l' map est beaucoup trop lisible. Mais il n'y a rien à craindre: nous pouvons utiliser la monade lois de l'élargir un peu. En particulier, fmap f x = x >>= return . f, de sorte

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

Nous pouvons point-gratuit-identifier, remplacez - (.) avec (<$>), puis ajouter quelques fausses sections:

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

La substitution de cette équation dans notre étape précédente:

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

Enfin, vous vous cassez la barre d'espace et de produire le merveilleux équation finale

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

Answer 2

A écrit une longue réponse à une pleine exécution par le biais de mes logs IRC des expériences qui mènent à la finale de code (c'était au début de 2008), mais j'ai accidentellement tout le texte :) Pas trop de perte de bien - pour la plupart de Daniel analyse est sur place.

Voici ce que j'ai commencé avec:

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

Les différences proviennent principalement vers le bas à l'ordre dans lequel les refactorings qui s'est passé.

• Au lieu de x = 1 : map (2*) x j'ai commencé avec 2 : map ..., et je l'ai gardé que 2 premières jusqu'à la toute dernière version, où j'ai serré dans un (*2) et changé l' $2 à la fin en $1. "Faites de la carte inutilement complexe" étape n'est pas arrivé (au début).
• J'ai utilisé liftM2 au lieu de liftA2
• L'obfuscation map fonction était de mettre en avant le remplacement de la liftM2 avec Applicative combinators. C'est également lors de tous les espaces ont disparu.
• Même ma "dernière" version eu beaucoup de . de la composition de fonctions. Le remplacement de tous ceux avec <$> , apparemment, est arrivé quelques fois dans le mois, entre ça et uncyclopedia.

BTW, voici une version mise à jour qui ne mentionne plus le nombre 2:

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