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

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

有人可以给我一些指针（不是一些内存地址，谢谢！）到底fix是什么。我从官方网站上的文档中知道一般定义。而且我在互联网上浏览了很多东西，只是找不到一个全面且易于理解的答案。

对我flip fix来说就像一个谜。在那个特定的函数调用中实际发生了什么？

顺便说一句，我只是在 2 个月前才拿起 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!"
4

2 回答 2

15

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)which is just putStrLn "abc"。因为函数\a b -> putStrLn "abc"忽略了它的第一个参数，所以fix从不递归。它实际上在这里仅用于混淆代码。

于 2013-03-20T12:39:27.223 回答
4

这只是编写递归 lambda 的一种有趣方式，我可以想到这样做的两种可能性：

  • 程序员想迷惑新手。
  • 他来自一种对递归更严格的语言（比如一些 LISP，或者可能是 ML？）

您可以更清晰地重写代码，例如：

    loop secret 0
where
    loop secret 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 secret numGuesses'

不同之处在于您必须secret手动传递，这可以通过递归 lambda 避免（这可能是使用 编写它的另一个原因fix）

为了更深入地了解修复，请搜索“y-combinator”

于 2013-03-20T12:28:54.410 回答