在阅读https://en.uncyclopedia.co/wiki/Haskell（并忽略所有“冒犯性”的东西）时，我偶然发现了以下一段混淆代码：
fix$(<$>)<$>(:)<*>((<$>((:[{- thor's mother -}])<$>))(=<<)<$>(*)<$>(*2))$1
ghci当我在（导入Data.Functionand之后Control.Applicative）运行那段代码时，ghci会打印出 2 的所有幂的列表。
这段代码是如何工作的？
问问题
15886 次
3 回答
222
首先，我们有一个可爱的定义
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)
于 2012-09-30T10:26:44.540 回答
15
正在写一个很长的答案，其中包含了导致最终代码的 IRC 实验日志的完整运行（这是在 2008 年初），但我不小心把所有的文本都写了:) 不过损失并不大 - 对于丹尼尔的大部分分析都是正确的。
这是我开始的：
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*) x我不是从.2 : map ..._ _ “使地图变得不必要的复杂”步骤并没有发生（那么早）。(*2)$2$1- 我使用 liftM2 而不是 liftA2
map在用 Applicative 组合器替换 liftM2 之前放入了混淆函数。这也是所有空间消失的时候。- 甚至我的“最终”版本也
.留下了很多用于功能组合的东西。<$>在这与非百科全书之间的几个月里，显然发生了替换所有这些的事情。
顺便说一句，这是一个不再提及数字的更新版本2：
fix$(<$>)<$>(:)<*>((<$>((:[{- Jörð -}])<$>))(=<<)<$>(*)<$>(>>=)(+)($))$1
于 2013-02-09T01:03:49.143 回答
4
这两个答案都从突然给出的简短原始代码中派生出混淆的代码片段，但问题实际上是在询问冗长的混淆代码如何完成其工作。
就是这样：
fix$(<$>)<$>(:)<*>((<$>((:[{- thor's mother -}])<$>))(=<<)<$>(*)<$>(*2))$1
= {- add spaces, remove comment -}
fix $ (<$>) <$> (:) <*> ( (<$> ((:[]) <$>) ) (=<<) <$> (*) <$> (*2) ) $ 1
-- \__\______________/_____________________________/
= {- A <$> B <*> C $ 1 = A (B 1) (C 1) -}
fix $ (<$>) (1 :) ( ( (<$> ((:[]) <$>) ) (=<<) <$> (*) <$> (*2) ) 1 )
-- \__\______________/____________________________/
= {- (<$>) A B = (A <$> B) ; (<$> B) A = (A <$> B) -}
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) 1 = A (B (C (D 1))) -}
fix $ (1 :) <$> (=<<) ( ((:[]) <$>) ( (*) ( (*2) 1 )))
= {- (*2) 1 = (1*2) = 2 -}
fix $ (1 :) <$> (=<<) ( ((:[]) <$>) ( (*) 2 ))
= {- (*) 2 = (2*) -}
fix $ (1 :) <$> (=<<) ( ((:[]) <$>) (2*) )
= {- ( A <$>) B = A <$> B -}
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] )
= {- (=<<) A = ( A =<<) -}
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]
通过类型应用和替换，我们看到有问题的 monad 是[]for which (>>= 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..]
于 2019-12-05T07:22:39.543 回答