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

これは、 を使用する簡略化されたバージョンですflip fix
おそらくGoogle Tech Talkまたは他のトークからのYouTubeビデオでこの使用方法を見ました。

誰かが私にいくつかのポインタ(メモリアドレスではありません、ありがとう!)を教えてもらえますかfix?公式サイトのドキュメントから一般的な定義を知っています。そして、私はインターネット上の多くのものをスキャンしましたが、包括的で理解しやすい答えを見つけることができませんでした.

そしてflip fix、私には謎のように見えます。その特定の関数呼び出しで実際に何が起こったのでしょうか?

ところで、Haskell を手に入れたのはちょうど 2 か月前のことです。そして、私は数学があまり得意ではありません:(


これは、そのプレゼンテーションを行った人が共有している完全なコードです。

(ああ、ここにゲームを説明するwikiリンクがあります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!"
4

2 に答える 2

15

fix固定小数点演算子です。おそらくその定義からわかるように、関数の固定小数点を計算します。これは、特定の関数について、次のようなf値を検索することを意味します。xf 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

これは、再帰ラムダを書く面白い方法です。なぜこれが行われるのか、2 つの可能性が考えられます。

  • プログラマーは初心者を混乱させたかった。
  • 彼は、再帰をより制限する言語から来ています (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手動で渡す必要があることです。これは、再帰ラムダによって回避されます (これは、 で記述する別の理由になる可能性がありますfix) 。

fix をより深く理解するには、「y-combinator」をググってください

于 2013-03-20T12:28:54.410 に答える