haskell - 翻转修复/修复

Question

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

这是使用的简化版本flip fix.
我在一些youtube视频中看到了这种方式,可能来自Google技术谈话或其他一些谈话.

有人可以给我一些指针(不是一些内存地址,谢谢!)究竟fix是什么.我知道官方网站上的文档的一般定义.我已经在互联网上浏览了很多东西,但却找不到一个全面且易于理解的答案.

flip fix对我来说,这看起来像个谜.那个特定的函数调用实际发生了什么？

顺便说一下,我2个月前才选择了Haskell.而且我不擅长数学:(

---

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

(哦,这是解释游戏的维基链接mastermind 点击)

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

Answer 1

fix是定点运算符.正如您可能从它的定义中知道的那样,它计算函数的固定点.这意味着,对于给定的函数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 fact'使用定义进行扩展fix,您将看到它与原始版本相同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不要递归.它实际上仅用于混淆代码.