[haskell] 이 난독 화 된 Haskell 코드는 어떻게 작동합니까?

Program / 글쓴이

https://en.uncyclopedia.co/wiki/Haskell을 읽는 동안 (그리고 “공격적인”모든 것을 무시하고) 다음과 같은 난독 화 된 코드를 발견했습니다.

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

에서 해당 코드를 실행하면 ghci( Data.Function및 가져 오기 후 Control.Applicative) ghci2의 모든 거듭 제곱 목록을 인쇄합니다.

이 코드는 어떻게 작동합니까?

답변

우선, 우리는 아름다운 정의를 가지고 있습니다.

x = 1 : map (2*) x

전에 본 적이 없다면 그 자체로 약간의 마음을 구부릴 수 있습니다. 어쨌든 그것은 게으름과 재귀의 상당히 표준적인 트릭입니다. 이제, fix및 point-free-ify를 사용하여 명시 적 재귀를 제거합니다 .

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

다음으로 할 일은 :섹션을 확장 하고 map불필요하게 복잡하게 만드는 것 입니다.

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

자, 이제 우리는 그 상수의 두 개의 복사본을 가지고 있습니다 1. 그것은 결코 할 수 없으므로 우리는 그것을 중복 제거하기 위해 적용되는 리더기를 사용할 것입니다. 또한 기능 구성은 약간 쓰레기이므로 (<$>)가능한 한 어디로 든 교체합시다 .

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

다음으로이 호출 map은 너무 읽기 쉽습니다. 그러나 두려워 할 것은 없습니다. 모나드 법칙을 사용하여 조금 확장 할 수 있습니다. 특히, fmap f x = x >>= return . f그래서

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

우리는 – 자유 쓸어 포인트 대체 할 수 (.)와 함께 (<$>)다음 몇 가지 가짜 섹션을 추가 :

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

이전 단계에서이 방정식을 대체합니다.

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

마지막으로 스페이스 바를 깨고 멋진 최종 방정식을 생성합니다.

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

답변

최종 코드 (2008 년 초)까지 이어지는 실험에 대한 IRC 로그 전체를 통해 긴 답변을 작성했지만 실수로 모든 텍스트를 작성했습니다. 대부분의 Daniel의 분석이 자리를 잡았습니다.

내가 시작한 것은 다음과 같습니다.

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

차이점은 대부분 리팩토링이 발생한 순서로 내려갑니다.

  • 대신 x = 1 : map (2*) xI로 시작 2 : map ..., 나는 내가 압착 맨 마지막 버전 때까지 초기 2 권리를 유지 (*2)하고 변화 $2에 끝 $1. “불필요 할 정도로 복잡한지도 만들기”단계는 발생하지 않았습니다.
  • 나는 liftA2 대신 liftM2를 사용했습니다.
  • 난독 화 된 map 함수는 liftM2를 Applicative combinators로 대체하기 전에 삽입되었습니다. 그 때도 모든 공간이 사라졌습니다.
  • 내 “최종”버전조차도 .함수 구성 을 위해 많은 부분 이 남아있었습니다. 그것들을 모두 대체하는 것은 그와 <$>백과 사전 사이의 몇 달 동안 일어난 것 같습니다.

BTW, 더 이상 번호를 언급하지 않는 업데이트 된 버전이 있습니다 2.

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

답변

두 답변 모두 파란색에서 제공된 짧은 원본에서 난독 화 된 코드 스 니펫을 파생하지만 실제로는 긴 난독 화 된 코드가 어떻게 작동하는지 묻습니다.

방법은 다음과 같습니다.

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

여기 ( (\ x -> [2*x]) =<<) = (>>= (\ x -> [2*x])) = concatMap (\ x -> [2*x]) = map (2*)에 함수가 있으므로 다시 <$> = .:

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

오름차순 으로 2의 모든 거듭 제곱입니다 .

이것은

  • A <$> B <*> C $ x = liftA2 A B C x이후 liftA2 A B C에 적용되는 x것이 함수 뜻 함수로서,하자 liftA2 A B C x = A (B x) (C x).
  • (f `op` g) = op f g = (f `op`) g = (`op` g) f 연산자 섹션의 세 가지 법칙입니다

  • >>=모나 딕 바인드이므로 (`op` g) f = op f g및 유형은

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

    유형 적용 및 대체에 의해 우리는 문제의 모나드가 []어떤 (>>= g) = concatMap g.

  • concatMap (\ x -> [2*x]) xs 다음과 같이 단순화됩니다.

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

  • 정의에 따라

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

    어디 

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

    그래서

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

답변