haskell - 翻转修复/修复 [英] haskell - flip fix / fix
问题描述
>>>>翻转修正（0 :: Int）（\ ab - > putStrLnabc）
输出：abc
这是使用翻转修正的简化版本。<
我看到过这种方式，可以在Google技术讲座或其他讲座中使用它。
有人可以给我一些指针（不是一些内存地址，谢谢！），究竟是什么 fix 是。我知道官方网站上文档的一般定义。我已经在互联网上扫描了很多东西，但找不到一个全面和简单易懂的答案。
和翻转修复对我来说只是一个谜。在那个特殊的函数调用中究竟发生了什么？
顺便说一句，我只是在2个月前挑选了Haskell。我不擅长数学：（$ / b>
这是一个完整的代码，由做这个的人共享演示文稿，如果有人感兴趣：
（哦，这里是wiki链接解释游戏 mastermind 点击）
模块Mastermind其中
导入Control.Monad
导入Data.Function
导入Data.List
导入System.Random
data Score = Score
{scoreRightPos :: Int
，scoreWrongPos :: Int
}
派生（Eq，Show）
实例读取得分其中
readsPrec_r = [（Score rp wp，t）
|（rp，s）< - readsPrec 11 r
，（wp，t）< - readsPrec 11 s
]
calcScore ::（等式a）=> [a] - > [a] - >得分
calcScore秘密猜测=得分rightPos wrongPos
其中
rightPos =长度[（）| （a，b）< - zip secret guess，a == b]
wrongPos =长度秘密 - 长度wrongTokens - rightPos
wrongTokens =猜测\\秘密
pool :: String
pool =rgbywo
universe :: [String]
universe = perms 4 pool
perms :: Int - > ; [a] - > [[a]]
perms n p = [s'| s< - 子序列p，长度s == n，s'< - 置换s]
chooseSecret :: IO String
chooseSecret = do
i < - randomRIO 0，长度宇宙 - 1）
回报$宇宙！ i
guessSecret :: [Score] - > [字符串] - > [String]
guessSecret _ [] = []
guessSecret〜（s：h）（g：u）= g：guessSecret h [g'| g'< - u，calcScore g'g == s]
playSecreter :: IO（）
playSecreter = do
secret < - chooseSecret
flip fix（0 :: Int）$ \loop numGuesses - >做
putStr猜测：
猜测< - getLine
让
得分= calcScore秘密猜测
numGuesses'= numGuesses + 1
打印分数
案例scoreRightPos评分
4 - > putStrLn $做得好，你猜对了++ show numGuesses'
_ - > loop numGuesses'
playBoth :: IO（）
playBoth = do
secret <--selectSecret
let
guessses = guessSecret得分宇宙
scores = map（calcScore secret）猜测
历史=拉链猜测分数
forM_ history $ \（guess，score） - >做
putStr猜：
putStrLn猜
打印分数
putStrLn $做得好，你在++显示（长度历史）中猜到
playGuesser :: IO（）
playGuesser = do
input< - getContents
let
guessses = guessSecret分数宇宙
分数=地图读取$行输入
history = zip猜测分数
forM_ guesses $ \guess - >做
putStrLn猜想
putStr得分：
案例snd $ $的最后历史b $ b得分4 0 - > putStrLn $做得好，我在++ show（历史长度）
_ - > putStrLn作弊！
f ，它会搜索一个值 x ，使得 fx == x 。
如何为任意函数找到这样的值？
我们可以查看 x 作为无穷项的结果 f（f（f ...）...））。显然，由于它是无限的，因此在它前面加上 f 并不会改变它，所以 fx 将会是与 x 相同。当然，我们不能表达一个无限的术语，但是我们可以将 fix 定义为 fix f = f（fix f） ，它表达了这个想法。
它有意义吗？
它会终止吗？是的，它会，但只是因为Haskell是一种懒惰的语言。如果 f 不需要它的参数，它不会计算它，所以计算会终止，它不会永久循环。如果我们在一个总是使用它的参数（它是严格的）的函数上调用 fix ，它永远不会终止。所以有些函数有一个固定的点，有些不是。 Haskell懒惰的评估确保我们计算它，如果存在的话。
为什么修复有用？
它表示递归。任何递归函数都可以使用 fix 来表示，而不需要任何额外的递归。所以 fix 是一个非常强大的工具！假设我们有
fact :: Int - > Int
fact 0 = 1
fact n = n * fact（n - 1）
我们可以使用 fix 来消除递归，如下所示：
fact :: Int - > Int
fact = fix fact'
where
fact'::（Int - > Int） - > Int - > Int
fact'_ 0 = 1
fact'rn = n * r（n - 1）
这里， fact'不是递归的。递归已移至 fix 中。这个想法是，如果需要的话， fact'作为第一个参数接受一个函数，它将用于递归调用。如果使用 fix 的定义展开 fix fact'，您会看到它与原始 fact 。
因此，您可以使用仅包含 code>运算符，否则不允许任何递归定义，并且您可以用递归定义表达所有可能的东西。
回到您的示例
让我们查看翻转修正（0 :: Int）（\ ab - > putStrLnabc），它只是修复（\ ab - > putStrLnabc）（0 :: Int）。现在让我们来评估一下：
修复（\ ab - > putStrLnabc）=
（\ ab - > putStrLnabc）（fix（\ ab - > putStrLnabc））=
\b - > putStrLnabc
因此整个表达式的计算结果为（\ b - > putStrLnabc）（0 :: Int），它只是 putStrLnabc。因为函数 \ a b - > putStrLnabc忽略它的第一个参数， fix 从不递归。它实际上仅用于混淆代码。
>>>flip fix (0 :: Int) (\a b -> putStrLn "abc")
Output: "abc"
This is a simplified version of using flip fix.
I saw this way of using it in some youtube video which are probably from google tech talk or some other talks.
Can somebody give me some pointers(not some memory address, thanks!) that what exactly fix is. I know the general definition from documentation on the official site. And I have scanned through lots of stuff on the internet, just couldn't find an answer that is comprehensive and simple to understand.
And flip fix just looks like a mystery to me. What actually happened in that particular function call?
BTW, I only picked Haskell up like 2 months ago. And I'm not very good at Math :(
This is the complete code, shared by the person who did that presentation, if anyone is interested:
(Oh, and here's the wiki link explaining the game mastermind Click)
module Mastermind where
import Control.Monad
import Data.Function
import Data.List
import System.Random
data Score = Score
{ scoreRightPos :: Int
, scoreWrongPos :: Int
}
deriving (Eq, Show)
instance Read Score where
readsPrec _ r = [ (Score rp wp, t)
| (rp, s) <- readsPrec 11 r
, (wp, t) <- readsPrec 11 s
]
calcScore :: (Eq a) => [a] -> [a] -> Score
calcScore secret guess = Score rightPos wrongPos
where
rightPos = length [() | (a, b) <- zip secret guess, a == b]
wrongPos = length secret - length wrongTokens - rightPos
wrongTokens = guess \\ secret
pool :: String
pool = "rgbywo"
universe :: [String]
universe = perms 4 pool
perms :: Int -> [a] -> [[a]]
perms n p = [s' | s <- subsequences p, length s == n, s' <- permutations s]
chooseSecret :: IO String
chooseSecret = do
i <- randomRIO (0, length universe - 1)
return $ universe !! i
guessSecret :: [Score] -> [String]-> [String]
guessSecret _ [] = []
guessSecret ~(s:h) (g:u) = g : guessSecret h [g' | g' <- u, calcScore g' g == s]
playSecreter :: IO ()
playSecreter = do
secret <- chooseSecret
flip fix (0 :: Int) $ \loop numGuesses -> do
putStr "Guess: "
guess <- getLine
let
score = calcScore secret guess
numGuesses' = numGuesses + 1
print score
case scoreRightPos score of
4 -> putStrLn $ "Well done, you guessed in " ++ show numGuesses'
_ -> loop numGuesses'
playBoth :: IO ()
playBoth = do
secret <- chooseSecret
let
guesses = guessSecret scores universe
scores = map (calcScore secret) guesses
history = zip guesses scores
forM_ history $ \(guess, score) -> do
putStr "Guess: "
putStrLn guess
print score
putStrLn $ "Well done, you guessed in " ++ show (length history)
playGuesser :: IO ()
playGuesser = do
input <- getContents
let
guesses = guessSecret scores universe
scores = map read $ lines input
history = zip guesses scores
forM_ guesses $ \guess -> do
putStrLn guess
putStr "Score: "
case snd $ last history of
Score 4 0 -> putStrLn $ "Well done me, I guessed in " ++ show (length history)
_ -> putStrLn "Cheat!"
fix is the fixed-point operator. As you probably know from it's definition, it computes the fixed point of a function. This means, for a given function f, it searches for a value x such that f x == x.
How to find such a value for an arbitrary function?
We can view x as the result of infinite term f (f (f ... ) ...)). Obviously, since it is infinite, adding f in front of it doesn't change it, so f x will be the same as x. Of course, we cannot express an infinite term, but we can define fix as fix f = f (fix f), which expresses the idea.
Does it makes sense?
Will it ever terminate? Yes, it will, but only because Haskell is a lazy language. If f doesn't need its argument, it will not evaluate it, so the computation will terminate, it won't loop forever. If we call fix on a function that always uses its argument (it is strict), it will never terminate. So some functions have a fixed point, some don't. And Haskell's lazy evaluation ensures that we compute it, if it exists.
Why is fix useful?
It expresses recursion. Any recursive function can be expressed using fix, without any additional recursion. So fix is a very powerful tool! Let's say we have
fact :: Int -> Int
fact 0 = 1
fact n = n * fact (n - 1)
we can eliminate recursion using fix as follows:
fact :: Int -> Int
fact = fix fact'
where
fact' :: (Int -> Int) -> Int -> Int
fact' _ 0 = 1
fact' r n = n * r (n - 1)
Here, fact' isn't recursive. The recursion has been moved into fix. The idea is that fact' accepts as its first argument a function that it will use for a recursive call, if it needs to. If you expand fix fact' using the definition of fix, you'll see that it does the same as the original fact.
So you could have a language that only has a primitive fix operator and otherwise doesn't permit any recursive definitions, and you could express everything you can with recursive definitions.
Back to your example
Let's view flip fix (0 :: Int) (\a b -> putStrLn "abc"), it is just fix (\a b -> putStrLn "abc") (0 :: Int). Now let's evaluate:
fix (\a b -> putStrLn "abc") =
(\a b -> putStrLn "abc") (fix (\a b -> putStrLn "abc")) =
\b -> putStrLn "abc"
So the whole expression evaluates to (\b -> putStrLn "abc") (0 :: Int) which is just putStrLn "abc". Because function \a b -> putStrLn "abc" ignores its first argument, fix never recurses. It's actually used here only to obfuscate the code.
这篇关于haskell - 翻转修复/修复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
