Jak działa ten zaciemniony kod Haskella?


90

Czytając https://en.uncyclopedia.co/wiki/Haskell (i ignorując wszystkie „obraźliwe” rzeczy), natknąłem się na następujący fragment zaciemnionego kodu:

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

Kiedy uruchamiam ten fragment kodu w ghci(po zaimportowaniu Data.Functioni Control.Applicative), ghciwyświetla listę wszystkich potęg 2.

Jak działa ten fragment kodu?


3
Zastanawiam się, czy odpowiedź byłaby czymś arystokratycznie obraźliwym ... jeśli to prawda, ironicznym, biorąc pod uwagę twoje wysiłki, aby uniknąć wulgarności.
Meredith,

31
Czego próbowałeś? Oczywistymi rzeczami do wypróbowania są (a) usunięcie komentarza, (b) przeformatowanie / przeformatowanie kodu, (c) ustalenie, które wystąpienia Functor / Applicative / Monad są używane (prawdopodobnie wszystkie listy, ale nie zakładaj ... . nic nie powstrzymałoby wystarczająco obłąkanego programisty przed użyciem pięciu różnych instancji Monady w jednej linii kodu), (d) uprościć tak bardzo, jak tylko możesz. Następnie zobacz, z czym zostało.
dave4420

10
Haskell to zdecydowanie mój ulubiony język programowania, ale mimo to niecyclopedia.wikia.com/wiki/Haskell tak bardzo mnie rozśmieszył!
AndrewC


5
Naprawdę denerwuje mnie, gdy ktoś znajduje najbardziej nieuzasadniony fragment kodu, jaki może znaleźć w języku XYZ, a następnie stwierdza, że ​​„praktycznie niemożliwe jest napisanie czytelnego kodu w języku XYZ”. Ale to tylko ja ...
MathematicalOrchid

Odpowiedzi:


218

Na początek mamy cudowną definicję

x = 1 : map (2*) x

co samo w sobie jest nieco zagmatwane, jeśli nigdy wcześniej go nie widziałeś. W każdym razie jest to dość standardowa sztuczka lenistwa i rekurencji. Teraz pozbędziemy się jawnej rekurencji przy użyciu fixi ify bez punktów.

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

Następną rzeczą, którą zamierzamy zrobić, jest rozszerzenie :sekcji i mapniepotrzebnie skomplikowane.

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

Cóż, teraz mamy dwie kopie tej stałej 1. To nigdy się nie uda, więc użyjemy aplikacji czytnika, aby to zduplikować. Również kompozycja funkcji to trochę bzdura, więc zastąpmy to (<$>)gdziekolwiek się da.

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

Dalej: to wezwanie mapjest zbyt czytelne. Ale nie ma się czego bać: możemy wykorzystać prawa monady, aby ją nieco rozszerzyć. W szczególności fmap f x = x >>= return . ftzw

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

Możemy wskazać-free-IFY wymienić (.)z (<$>), a następnie dodać kilka odcinków fałszywe:

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

Zastępując to równanie w naszym poprzednim kroku:

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

Na koniec łamiesz spację i tworzysz wspaniałe końcowe równanie

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

4
Zostawiłeś {- thor's mother -}!
Simon Shine,

13

Pisałem długą odpowiedź z pełnym przebiegiem moich dzienników IRC z eksperymentów prowadzących do ostatecznego kodu (to było na początku 2008 roku), ale przypadkowo cały tekst :) Jednak nie tak duża strata - dla w większości analizy Daniela są trafne.

Oto, od czego zacząłem:

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

Różnice sprowadzają się głównie do kolejności przeprowadzania refaktoryzacji.

  • Zamiast tego x = 1 : map (2*) xzacząłem od 2 : map ...i zachowałem te początkowe 2 aż do ostatniej wersji, w której wcisnąłem a (*2)i zmieniłem $2na końcu na $1. Krok „uczyń mapę niepotrzebnie złożoną” nie nastąpił (tak wcześnie).
  • Użyłem liftM2 zamiast liftA2
  • Funkcja zaciemniona mapzostała wprowadzona przed zastąpieniem liftM2 kombinatorami Applicative. Wtedy też zniknęły wszystkie przestrzenie.
  • Nawet moja „ostateczna” wersja miała jeszcze wiele .funkcji do komponowania. Zastąpienie tych wszystkich <$>najwyraźniej wydarzyło się jakiś czas w miesiącach między tym a niecyklopedią.

Przy okazji, oto zaktualizowana wersja, która nie wymienia już numeru 2:

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

10
Czy pominięcie słowa „skreślony” w pierwszym akapicie jest zamierzone? Jeśli tak, to moja głowa do pana.
Jake Brownson,

3
@JakeBrownson To popularny idiom internetowy , chociaż nie jestem też pewien, czy był to celowy.
Lambda Fairy,

1

Obie odpowiedzi wywodzą zaciemniony fragment kodu z krótkiego oryginału podanego nieoczekiwanie, ale pytanie w rzeczywistości dotyczy tego, w jaki sposób długi zaciemniony kod wykonuje swoją pracę.

Oto jak:

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

Oto ( (\ x -> [2*x]) =<<) = (>>= (\ x -> [2*x])) = concatMap (\ x -> [2*x]) = map (2*)funkcja, więc znowu <$> = .:

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

są wszystkie potęgi 2 , w porządku rosnącym.


To używa

  • A <$> B <*> C $ x = liftA2 A B C xa ponieważ liftA2 A B Cjest stosowany do xswojej funkcji, to oznacza jako funkcję liftA2 A B C x = A (B x) (C x).
  • (f `op` g) = op f g = (f `op`) g = (`op` g) f są trzema prawami sekcji operatora
  • >>=jest monadycznym wiązaniem, a ponieważ (`op` g) f = op f gi typy są

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

    według zastosowania typu i podstawienia widzimy, że dana monada jest []dla której (>>= g) = concatMap g.

  • concatMap (\ x -> [2*x]) xs jest uproszczony jako

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

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

    gdzie

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

    po to aby

    ((2*)^n) 1  =  ((2*) . (2*) .  ...  . (2*)) 1
                =    2*  (  2*  (  ...  (  2*   1 )...)) 
                =    2^n   ,  for n in [0..]
    
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.