haskell - флип фикс/фикс

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

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

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

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

Кстати, я взял Haskell всего 2 месяца назад. И я не очень силен в математике :(


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

(О, и вот вики-ссылка, объясняющая игру 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!"

person pochen    schedule 20.03.2013    source источник
comment
К вашему сведению, речь шла о реализации игры Mastermind, предоставленной Питером Марксом из London Haskell Users' Group.   -  person Tom Ellis    schedule 15.11.2013


Ответы (2)


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 никогда не повторяется. На самом деле он используется здесь только для запутывания кода.

person Petr    schedule 20.03.2013
comment
Как чудесно! Я как раз случайно смотрю еще одно видео о лени, когда вижу ваше объяснение, спикер - Саймон Пейтон Джонс! Лень ради победы. Я не знал, что fix может завершаться только потому, что это Haskell! - person pochen; 20.03.2013
comment
Таким образом, fact' является первым аргументом самого себя, а аргумент Int (0 в первом сопоставлении с образцом, n во втором сопоставлении с образцом) точно такой же, как единственный ( опущен) аргумент для fact. Это правильно? @Петр Пудлак - person pochen; 20.03.2013
comment
@prM Первый аргумент fact' на самом деле fix fact'. Мы говорим fact' что-то вроде вычисления одного уровня вычислений и даем вам рекурсивную версию себя, если вам нужно. Функция fact' имеет тип (Int -> Int) -> (Int -> Int), и когда мы применяем к ней fix, мы вычисляем ее фиксированную точку типа (Int -> Int). Таким образом, результат с фиксированной точкой является функцией! Вот почему у нас там всего fix fact'. И вы правы, второй аргумент Int для fact' соответствует единственному аргументу fact. - person Petr; 20.03.2013
comment
Статья @prM в Википедии Комбинатор фиксированной точки также содержит ценную информацию. Если вы также изучаете лямбда-исчисление, вас может заинтересовать четкий, интуитивно понятный вывод комбинатора с фиксированной точкой (комбинатор Y )?. Комбинатор Y в основном то же самое, что и fix, только выраженный в нетипизированном лямбда-исчислении. (В Haskell мы определяем fix как рекурсивную функцию, но в нетипизированном лямбда-исчислении мы можем определить этот оператор как лямбда-член без какой-либо рекурсии.) - person Petr; 20.03.2013
comment
Я уже писал flip fix в производственном коде. У него есть пара применений. flip fix arg0 $ \loop arg -> do { ... something that uses loop conditionally, passing in a new value for arg ...}, в частности. Меньше скобок и дополнительных определений при создании рекурсивных функций внутри блока do, которые зависят от имен, уже привязанных к области действия блока do. - person Carl; 20.03.2013
comment
Отличный ответ. Однако я хотел бы подчеркнуть две вещи: (а) стоит явно указать, что первое уравнение для fact', fact' _ 0 = 1 не использует свой первый аргумент, как в этом случае происходит выход из бесконечного стека fact' (fact' (...)); (b) хотя определение fix f = f (fix f) проще для понимания, более практичной альтернативой является fix f = let r = f r in r, которое более удобно для производительности; простая компилируется в код, который выделяет новый преобразователь на каждом шаге, в то время как версия let приводит к циклическим эталонным графам, которые повторно используют одни и те же преобразователи. - person Luis Casillas; 20.03.2013
comment
Спасибо @PetrPudlák! Впечатляющие ответы! И последнее, чего я не понимаю, как тип fix fact' вписывается в fact'? - person pochen; 21.03.2013
comment
Спасибо @sacundim! Всегда полезно узнать больше о производительности :) - person pochen; 21.03.2013
comment
@prM Подумайте, что делает fix f - он ищет x, чтобы f x = x. Это означает, что f должна быть функцией некоторого типа от a до a, другими словами f :: a -> a. И его фиксированная точка, конечно, того же типа, что и аргумент и результат f - fix f :: a. Таким образом, только fix имеет тип fix :: (a -> a) -> a. В случае с fact' нашим a будет Int -> Int. Итак, fact' :: (Int -> Int) -> (Int -> Int) и fix fact' :: Int -> Int. - person Petr; 21.03.2013

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

  • Программист хотел запутать новичков.
  • Он исходит из языка, который более строг с рекурсией (например, какой-то 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)

Для более глубокого понимания исправления погуглите "y-combinator"

person Ingo    schedule 20.03.2013