Haskell - исправление/исправить флип

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

Это упрощенная версия использования flip fix.
Я видел этот способ использования этого в некоторых видео на YouTube, которые, вероятно, связаны с технологией Google Talk или некоторыми другими разговорами.

Может кто-нибудь дать мне несколько указателей (а не какой-то адрес памяти, спасибо!), что именно 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!"

Ответ 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 никогда не повторяется. Он фактически используется здесь только для обфускации кода.

Ответ 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, goog для "y-combinator"