gpt4 book ai didi

haskell - 翻转修复/修复

转载 作者:行者123 更新时间:2023-12-02 10:49:20 28 4
gpt4 key购买 nike

>>>flip fix (0 :: Int) (\a b -> putStrLn "abc")
Output: "abc"

这是使用翻转修复的简化版本。
我在一些 YouTube 视频中看到了这种使用方式,这些视频可能来自谷歌技术演讲或其他一些演讲。

有人能给我一些指示(不是一些内存地址,谢谢!)fix 到底是什么。我从官方网站上的文档中知道了一般定义。而且我在网上查了很多资料,就是找不到全面且简单易懂的答案。

翻转修复对我来说就像一个谜。在该特定函数调用中实际发生了什么?

顺便说一句,我大约两个月前才选择 Haskell。而且我数学不太好:(

<小时/>

这是完整的代码,由进行该演示的人共享,如果有人感兴趣的话:

(哦,这是解释游戏 mastermind Click 的 wiki 链接)

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!"

最佳答案

修复fixed-point operator 。正如您可能从它的定义中知道的那样,它计算函数的不动点。这意味着,对于给定函数 f,它会搜索值 x,使得 f x == x

如何为任意函数找到这样的值?

我们可以将x视为无限项f (f (f ... ) ...))的结果。显然,由于它是无限的,所以在它前面添加 f 不会改变它,因此 f x 将与 x 相同。当然,我们不能表达无限项,但是我们可以将fix定义为fix f = f (fix f),它表达了这个想法。

这有意义吗?

它会终止吗?是的,会的,但只是因为 Haskell 是一种懒惰的语言。如果 f 不需要它的参数,它不会计算它,因此计算将终止,它不会永远循环。如果我们在一个始终使用其参数(严格的)的函数上调用 fix ,它永远不会终止。所以有些函数有不动点,有些则没有。 Haskell 的惰性求值确保我们计算它(如果存在)。

为什么fix有用?

表示递归。任何递归函数都可以使用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' r n = n * r (n - 1)

这里,fact' 不是递归的。递归已移至 fix 中。这个想法是,fact' 接受一个函数作为其第一个参数,如果需要的话,它将用于递归调用。如果您使用 fix 的定义扩展 fix fact',您会发现它与原始 fact 的作用相同。

因此,您可以拥有一种仅具有原始 fix 运算符的语言,否则不允许任何递归定义,并且您可以使用递归定义来表达您可以表达的一切。

回到你的例子

让我们看看flip fix (0::Int) (\a b -> putStrLn "abc"),它只是fix (\a b -> putStrLn "abc") (0::Int)。现在我们来评估一下:

fix (\a b -> putStrLn "abc") =
(\a b -> putStrLn "abc") (fix (\a b -> putStrLn "abc")) =
\b -> putStrLn "abc"

因此,整个表达式的计算结果为 (\b -> putStrLn "abc") (0::Int),即 putStrLn "abc"。因为函数 \a b -> putStrLn "abc" 忽略其第一个参数,所以 fix 永远不会递归。它实际上在这里只是用来混淆代码。

关于haskell - 翻转修复/修复,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15523093/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com