haskell - odwróć fix/fix

Question

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

To jest uproszczona wersja korzystania z flip fix.
Widziałem ten sposób użycia go w niektórych filmach na youtube, które prawdopodobnie pochodzą z google tech talk lub innych rozmów.

Czy ktoś może mi dać kilka wskazówek (nie jakiś adres pamięci, dzięki!), Że to co jest dokładnie fix. Znam ogólną definicję z dokumentacji na oficjalnej stronie. I przeskanowałem wiele rzeczy w Internecie, po prostu nie mogłem znaleźć odpowiedzi, która byłaby obszerna i łatwa do zrozumienia.

I flip fix właśnie wygląda dla mnie tajemnicą. Co tak naprawdę stało się w tym konkretnym wywołaniu funkcji?

BTW, ja tylko podniósł Haskell się jak 2 miesiące temu. I nie jestem bardzo dobry w matematyce :(

---

To jest kompletny kod, udostępniane przez osobę, która zrobiła prezentację, jeśli ktoś jest zainteresowany:

(Oh, a oto link wiki wyjaśniając grę 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 jest fixed-point operator. Jak zapewne wiesz z jego definicji, oblicza stały punkt funkcji. Oznacza to, dla danej funkcji f, wyszukuje wartości x takie, że f x == x.

Jak znaleźć taką wartość dla dowolnej funkcji?

Możemy zobaczyć x w wyniku nieskończonego terminu f (f (f ...) ...)). Oczywiście, ponieważ jest nieskończony, dodanie przed nim f go nie zmienia, więc f x będzie takie samo jak x. Oczywiście nie możemy wyrazić nieskończonego terminu, ale możemy zdefiniować fix jako fix f = f (fix f), który wyraża ideę.

Czy ma to sens?

Czy kiedykolwiek się zakończy? Tak, będzie, ale tylko dlatego, że Haskell jest leniwym językiem.Jeśli f nie potrzebuje swojego argumentu, nie będzie go oceniał, więc obliczenia zakończą się, nie będzie pętli na zawsze. Jeśli wywołasz fix na funkcji, która zawsze używa jej argumentu (jest ścisły), nigdy się nie zakończy. Niektóre funkcje mają stały punkt, inne nie. I leniwa ocena Haskella zapewnia, że ​​ją obliczymy, jeśli istnieje.

Dlaczego fix przydatna?

Wyraża rekursję. Każda funkcja rekurencyjna może być wyrażona za pomocą fix, bez dodatkowej rekursji. Tak więc fix jest bardzo potężnym narzędziem! Powiedzmy, że mamy

fact :: Int -> Int 
fact 0 = 1 
fact n = n * fact (n - 1) 

możemy wyeliminować rekurencji przy użyciu fix następująco:

fact :: Int -> Int 
fact = fix fact' 
    where 
    fact' :: (Int -> Int) -> Int -> Int 
    fact' _ 0 = 1 
    fact' r n = n * r (n - 1) 

Tutaj fact' nie jest rekurencyjny. Rekursja została przeniesiona do fix. Chodzi o to, że fact' przyjmuje jako pierwszy argument funkcję, której będzie używał do wywołania rekursywnego, jeśli zajdzie taka potrzeba. Jeśli rozwinąć fix fact' przy użyciu definicji fix, zobaczysz, że robi to tak samo jak oryginalny fact.

Można więc używać języka, który ma tylko prymitywny operator fix, a poza tym nie zezwala na definicje rekursywne i można wyrazić wszystko, co można, za pomocą definicji rekursywnych.

Powrót do przykładu

widoku Miejmy flip fix (0 :: Int) (\a b -> putStrLn "abc"), to tylko fix (\a b -> putStrLn "abc") (0 :: Int). Teraz ocenić:

fix (\a b -> putStrLn "abc") = 
(\a b -> putStrLn "abc") (fix (\a b -> putStrLn "abc")) = 
\b -> putStrLn "abc" 

Więc całe wyrażenie do (\b -> putStrLn "abc") (0 :: Int) który jest po prostu putStrLn "abc". Ponieważ funkcja \a b -> putStrLn "abc" ignoruje pierwszy argument, fix nigdy się nie powtórzy. Używa się go tutaj jedynie do zaciemnienia kodu.

Answer 2

to tylko zabawny sposób napisać rekurencyjne lambda, mogę myśleć o dwóch możliwościach dlaczego odbywa się to:

• Programista chciał pomylić początkujących.
• Pochodzi z języka, który jest bardziej restrykcyjny z rekursji

Można przepisać kod znacznie jaśniejsze podobne (jak jakiś LISP lub ML może?):

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' 

tą różnicą, że musisz ręcznie zdać secret, czego uniknąć można przez rekursywną lambdę (i może to być kolejny powód, aby go zapisać z fix)

Aby uzyskać głębsze zrozumienie poprawki, użyj klawisza "y-combinator"