haskell - 翻转修复/修复

本文介绍了haskell - 翻转修复/修复的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 >>>>翻转修正（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），（wp，t）] 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 回报$宇宙！ 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 flip fix（0 :: Int）$ \loop numGuesses - >做 putStr猜测：猜测< - getLine 让得分= calcScore秘密猜测 numGuesses'= numGuesses + 1 打印分数案例scoreRightPos评分 4 - > putStrLn $做得好，你猜对了++ show numGuesses' _ - > loop numGuesses' playBoth :: IO（） playBoth = do secret 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作弊！ 解决方案 fix 是定点运营商。正如你可能从它的定义中知道的那样，它计算一个函数的固定点。这意味着，对于给定的函数 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 whereimport Control.Monadimport Data.Functionimport Data.Listimport System.Randomdata 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] -> ScorecalcScore secret guess = Score rightPos wrongPos where rightPos = length [() | (a, b) <- zip secret guess, a == b] wrongPos = length secret - length wrongTokens - rightPos wrongTokens = guess \\ secretpool :: Stringpool = "rgbywo"universe :: [String]universe = perms 4 poolperms :: Int -> [a] -> [[a]]perms n p = [s' | s <- subsequences p, length s == n, s' <- permutations s]chooseSecret :: IO StringchooseSecret = do i <- randomRIO (0, length universe - 1) return $ universe !! iguessSecret :: [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 havefact :: Int -> Intfact 0 = 1fact n = n * fact (n - 1)we can eliminate recursion using fix as follows:fact :: Int -> Intfact = 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 exampleLet'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 - 翻转修复/修复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！