haskell - флип-исправление/исправление

Question

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

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

Может кто-нибудь дать мне несколько указателей (не какой-то адрес памяти, спасибо!), Что точно fix есть. Я знаю общее определение из документации на официальном сайте. И я просмотрел множество материалов в Интернете, просто не мог найти ответ, который является всеобъемлющим и простым для понимания.

И flip fix просто выглядит для меня загадкой. Что на самом деле произошло в этом конкретном вызове функции?

BTW, я выбрал Haskell, как 2 месяца назад. И я не очень хорошо в математике :(

---

Это полный код, разделяемый человек, который сделал это представление, если кому-то интересно:

(О, а вот ссылка на вики объясняя игру mastermindClick)

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 является 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 на функцию, которая всегда использует свой аргумент (она строгая), она никогда не завершится. Поэтому некоторые функции имеют фиксированную точку, некоторые - нет. И ленивая оценка Хаскелла гарантирует, что мы ее вычислим, если она существует.

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

Answer 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)

для более глубокого понимания затруднительного, GOOG для «у-комбинатора»