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