Haskell Language
무료 모나드

무료 모나드는 모나드 계산을 데이터 구조와 해석기로 나눕니다.

예를 들어, 프롬프트에서 읽고 쓰는 명령과 관련된 계산 :

먼저 우리 계산의 "명령"을 Functor 데이터 형식으로 설명합니다

{-# LANGUAGE DeriveFunctor #-}

data TeletypeF next
    = PrintLine String next
    | ReadLine (String -> next)
    deriving Functor

그런 다음 Free 를 사용하여 "Free Monad over TeletypeF "를 만들고 기본 작업을 작성합니다.

import Control.Monad.Free (Free, liftF, iterM)

type Teletype = Free TeletypeF

printLine :: String -> Teletype ()
printLine str = liftF (PrintLine str ())

readLine :: Teletype String
readLine = liftF (ReadLine id)

f 가 Functor 일 때마다 Free f 는 Monad 이므로 표준 Monad 결합 자 ( do notation 포함)를 사용하여 Teletype 계산을 할 수 있습니다.

import Control.Monad -- we can use the standard combinators

echo :: Teletype ()
echo = readLine >>= printLine

mockingbird :: Teletype a
mockingbird = forever echo

마지막으로 우리는 Teletype a 가치 Teletype a 것으로 바꾸는 "통역사"를 작성하여 우리가 IO a 와 같이 작업하는 방법을 알고 있습니다 IO a

interpretTeletype :: Teletype a -> IO a
interpretTeletype = foldFree run where
  run :: TeletypeF a -> IO a
  run (PrintLine str x) = putStrLn *> return x
  run (ReadLine f) = fmap f getLine

우리는 Teletype a 을 IO Teletype a 계산을 "실행"하는데 사용할 수 있습니다.

> interpretTeletype mockingbird
hello
hello
goodbye
goodbye
this will go on forever
this will go on forever

무료 모나드는 고정 점과 같습니다.

Free 의 정의와 Fix 의 정의를 비교하십시오.

data Free f a = Return a
              | Free (f (Free f a))

newtype Fix f = Fix { unFix :: f (Fix f) }

특히, Free 생성자의 유형을 Fix 생성자의 유형과 비교하십시오. Free 층까지 단지 같은 펑 Fix 하는 것을 제외하고, Free 추가가 Return a 케이스.

foldFree와 iterM은 어떻게 작동합니까?

해체하는 데 도움이되는 몇 가지 기능이 있습니다 Free 다른 모나드로 해석하여 계산을 m : iterM :: (Functor f, Monad m) => (f (ma) -> ma) -> (Free fa -> ma) 및 foldFree :: Monad m => (forall x. fx -> mx) -> (Free fa -> ma) . 그들이 뭐하고 있니?

우선 Teletype a 함수를 IO 수동으로 해석하는 것을 해체하는 데 필요한 것이 무엇인지 살펴 봅시다. Free fa 가 정의 된 것으로 볼 수 있습니다.

data Free f a 
    = Pure a 
    | Free (f (Free f a))

Pure 경우는 쉽습니다.

interpretTeletype :: Teletype a -> IO a
interpretTeletype (Pure x) = return x
interpretTeletype (Free teletypeF) = _

이제 Free 생성자로 Teletype 계산을 해석하는 방법은 무엇입니까? 우리는 teletypeF :: TeletypeF (Teletype a) 를 검사하여 IO a 유형의 값에 도달하려고합니다. 먼저, 모나드의 단일 레이어를 IO 액션에 매핑하는 runIO :: TeletypeF a -> IO a a 함수를 작성합니다.

runIO :: TeletypeF a -> IO a
runIO (PrintLine msg x) = putStrLn msg *> return x
runIO (ReadLine k) = fmap k getLine

이제 runIO 를 사용하여 나머지 interpretTeletype 을 채울 수 있습니다. teletypeF :: TeletypeF (Teletype a) 는 나머지 Free 계산을 포함하는 TeletypeF 펑터의 계층입니다. 우리는 runIO 를 사용하여 최 외곽 계층을 해석합니다 ( runIO teletypeF :: IO (Teletype a) ). 그리고 나서 IO 모나드의 >>= combinator를 사용하여 리턴 된 Teletype a 을 해석합니다.

interpretTeletype :: Teletype a -> IO a
interpretTeletype (Pure x) = return x
interpretTeletype (Free teletypeF) = runIO teletypeF >>= interpretTeletype

의 정의 foldFree 단지 중 하나입니다 interpretTeletype 것을 제외하고, runIO 기능을 밖으로 고려하고있다. 결과적으로 foldFree 는 특정 기본 함수기 및 대상 모나드와 독립적으로 작동합니다.

foldFree :: Monad m => (forall x. f x -> m x) -> Free f a -> m a
foldFree eta (Pure x) = return x
foldFree eta (Free fa) = eta fa >>= foldFree eta

foldFree 는 rank-2 유형을 가지고 있습니다. eta 는 자연스러운 변형입니다. 우리는 foldFree 에 Monad m => (f (Free fa) -> m (Free fa)) -> Free fa -> ma 를 부여 할 수 있었지만, 이는 eta 에게 f 층 안의 Free 계산을 검사 할 수있는 자유를 eta . foldFree 하면이 제한적인 유형으로 eta 가 한 번에 하나의 레이어 만 처리 할 수 ​​있습니다.

iterM 은 접기 기능에 하위 계산을 검사하는 기능을 제공합니다. 이전 반복의 (모나드) 결과는 f 의 매개 변수 내에서 다음에 사용할 수 있습니다. iterM A와 유사 paramorphism 반면 foldFree 유사한 것이다 catamorphism .

iterM :: (Monad m, Functor f) => (f (m a) -> m a) -> Free f a -> m a
iterM phi (Pure x) = return x
iterM phi (Free fa) = phi (fmap (iterM phi) fa)

프리어 모나드

Freer (또는 Prompt, Operational) 모나드라고 불리는 무료 모나드의 다른 공식이 있습니다. 프리어 모나드는 기본 명령 세트에 Functor 인스턴스가 필요 없으며 표준 프리 모나드와 비교할 때 목록과 비슷한 구조를가집니다.

Freer 모나드는 프로그램을 명령어 세트 i :: * -> * 속하는 원자 명령어 의 시퀀스로 나타냅니다. 각 명령어는 매개 변수를 사용하여 반환 유형을 선언합니다. 예를 들어, State 모나드에 대한 기본 명령어 세트는 다음과 같습니다.

data StateI s a where
    Get :: StateI s s  -- the Get instruction returns a value of type 's'
    Put :: s -> StateI s ()  -- the Put instruction contains an 's' as an argument and returns ()

이러한 명령어의 시퀀싱은 :>>= 생성자로 수행됩니다. :>>= 복귀 단일 명령어 얻어 a 상기 연속으로 반환 값 배관 프로그램의 나머지를 앞에 추가. 환언에서, 복귀 인스트럭션 주어진 a , 그리고 회전하는 기능 a 복귀 프로그램에 b , :>>= 복귀 프로그램을 생성한다 b .

data Freer i a where
    Return :: a -> Freer i a
    (:>>=) :: i a -> (a -> Freer i b) -> Freer i b

a 는 실재로 :>>= 생성자로 계량됩니다. 통역사가 GADT i 에서 패턴 매칭을 통해 무엇인지 알 수 a 유일한 방법은.

제외 : 공동는-요 네다 보조 정리는 것을 우리에게 알려줍니다 Freer 동형입니다 Free . CoYoneda functor의 정의를 상기 CoYoneda .

data CoYoneda i b where
  CoYoneda :: i a -> (a -> b) -> CoYoneda i b

Freer i 는 Free (CoYoneda i) 와 동등합니다. Free 의 생성자 를 가져 와서 f ~ CoYoneda i 설정하면 다음을 얻게됩니다.

Pure :: a -> Free (CoYoneda i) a
Free :: CoYoneda i (Free (CoYoneda i) b) -> Free (CoYonda i) b ~
        i a -> (a -> Free (CoYoneda i) b) -> Free (CoYoneda i) b

이로부터 우리는 복구 할 수 있습니다 Freer i 단지 설정의 생성자를 Freer i ~ Free (CoYoneda i) .

때문에 CoYoneda i A는 Functor 어떤을위한 i , Freer A는 Monad 어떤을위한 i 경우에도, i 하지 않은 것입니다 Functor .

instance Monad (Freer i) where
    return = Return
    Return x >>= f = f x
    (i :>>= g) >>= f = i :>>= fmap (>>= f) g  -- using `(->) r`'s instance of Functor, so fmap = (.)

인터프리터는 명령어를 일부 처리기 모나드에 매핑하여 Freer 용으로 빌드 할 수 있습니다.

foldFreer :: Monad m => (forall x. i x -> m x) -> Freer i a -> m a
foldFreer eta (Return x) = return x
foldFreer eta (i :>>= f) = eta i >>= (foldFreer eta . f)

예를 들어 정규 State s 모나드를 처리기로 사용하여 Freer (StateI s) 모나드를 해석 할 수 있습니다.

runFreerState :: Freer (StateI s) a -> s -> (a, s)
runFreerState = State.runState . foldFreer toState
    where toState :: StateI s a -> State s a
          toState Get = State.get
          toState (Put x) = State.put x