Haskell Cont 모나드는 어떻게 그리고 왜 작동합니까?

Haskell Cont 모나드는 어떻게 그리고 왜 작동합니까?

---

Cont 모나드는 다음과 같이 정의됩니다.

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

instance Monad (Cont r) where
    return a = Cont ($ a)
    m >>= k  = Cont $ \c -> runCont m $ \a -> runCont (k a) c

이것이 어떻게 그리고 왜 작동하는지 설명해 주시겠습니까? 무엇을하고 있습니까?

---

연속 모나드에 대해 가장 먼저 깨달은 것은 근본적으로 실제로 는 아무것도 하지 않는다는 것 입니다. 사실이에요!

일반적으로 연속의 기본 개념은 계산의 나머지 부분을 나타내는 것 입니다. 다음과 같은 표현식이 있다고 가정 foo (bar x y) z합니다.. 이제 괄호로 묶인 부분 만 추출합니다. bar x y이 부분 은 전체 표현식의 일부 이지만 적용 할 수있는 함수는 아닙니다. 대신에 함수 를 적용해야 합니다 . 따라서이 경우 "나머지 계산"에 대해 \a -> foo a z라고 말할 수 있습니다 bar x y. 이는 완전한 형태를 재구성하는 데 적용 할 수 있습니다 .

이제 "나머지 계산"이라는 개념이 유용하지만, 우리가 고려하고있는 하위 표현을 벗어난 것이기 때문에 작업하기가 어색합니다. 일이 더 잘 작동하도록하기 위해 우리는 모든 것을 뒤집을 수 있습니다. 관심있는 하위 표현식을 추출한 다음 나머지 계산을 나타내는 인수를받는 함수로 래핑합니다 \k -> k (bar x y).

이 수정 된 버전은 우리에게 많은 유연성을 제공합니다. 컨텍스트에서 하위 표현식을 추출 할뿐만 아니라 하위 표현식 자체 내에서 외부 컨텍스트를 조작 할 수 있습니다 . 우리는 이것을 일종의 일시 중단 된 계산 으로 생각할 수 있으며 다음에 일어날 일을 명시 적으로 제어 할 수 있습니다. 자, 이것을 어떻게 일반화 할 수 있을까요? 음, 하위 표현식은 거의 변경되지 않았으므로 인사이드 아웃 함수에 대한 매개 변수로 \x k -> k x바꾸면됩니다. 즉, 함수 응용 프로그램에 지나지 않습니다 . reversed . 우리는 쉽게 작성 flip ($)하거나 이국적인 외국어 풍미를 약간 추가하고 그것을 연산자로 정의 할 수 |>있습니다.

이제 표현의 모든 조각을이 형식으로 번역하는 것은 간단하고 지루하고 끔찍하게 난독 화 될 것입니다. 다행히 더 좋은 방법이 있습니다. Haskell 프로그래머로서 백그라운드 컨텍스트 내에서 계산을 구축하는 것을 생각할 때 다음으로 생각 하는 것은 모나드입니까? 이 경우 대답은 yes 입니다. 그렇습니다.

이것을 모나드로 바꾸려면 두 가지 기본 구성 요소로 시작합니다.

• 모나드 m의 경우 type m a값은 a모나드 컨텍스트 내에서 유형 값에 액세스 할 수 있음을 나타냅니다 .
• "일시 중단 된 계산"의 핵심은 뒤집힌 함수 응용 프로그램입니다.

a이 컨텍스트 내 에서 특정 유형에 액세스한다는 것은 무엇을 의미 합니까? 그것은 단지 일부 값에 대해 그 의미 x :: a, 우리가 적용한 flip ($)로 x우리에게 형식의 인수를 취하는 함수를받는 함수를 제공 a하고, 해당 기능을 적용합니다 x. type 값을 보유하는 일시 중단 된 계산이 있다고 가정 해 보겠습니다 Bool. 이것은 우리에게 어떤 유형을 제공합니까?

> :t flip ($) True
flip ($) True :: (Bool -> b) -> b

따라서 일시 중단 된 계산의 경우 유형 m a은 (a -> b) -> b...로 작동합니다 . 우리는 이미에 대한 서명을 알고 있었기 때문에 아마도 반절 정일 수 Cont있지만 지금은 저를 유머러스하게 생각합니다.

여기서 주목해야 할 흥미로운 점은 일종의 "역전"이 모나드의 유형에도 적용 Cont b a된다는 것입니다. 함수를 취하고로 a -> b평가 되는 함수를 나타냅니다 b. 연속은 계산의 "미래"를 a나타내므로 서명 의 유형 은 어떤 의미에서 "과거"를 나타냅니다.

그래서, 교체 (a -> b) -> b로 Cont b a, 역 기능을 응용 프로그램의 우리의 기본적인 빌딩 블록의 모나드 타입은 무엇인가? a -> (a -> b) -> b는 a -> Cont b a...와 동일한 유형의 시그니처로 번역 return되며 실제로 그게 바로 그 자체입니다.

이제부터는 모든 것이 유형에서 직접적으로 나옵니다 >>=. 실제 구현 외에는 실질적으로 구현할 수 있는 합리적인 방법이 없습니다 . 하지만 실제로 무엇을 하고 있습니까?

이 시점에서 우리는 내가 처음에 말한 것으로 돌아갑니다. 연속 모나드는 실제로 많은 일을 하지 않습니다 . 유형의 Cont r a무언가는 a단순히 id일시 중단 된 계산에 대한 인수로 제공함으로써 단순한 유형의 무언가와 사소하게 동등합니다 . 이것은 하나의 경우, 여부를 물어 이어질 수도 Cont r a모나드하지만 변환이 너무 사소한, 안 a혼자 도 모나드 수? 물론 Monad인스턴스 로 정의 할 유형 생성자가 없기 때문에있는 그대로 작동하지 않지만 data Id a = Id a. 이것은 실제로 모나드, 즉 신원 모나드입니다.

무엇 않습니다 >>=신원 모나드에 대한합니까? 형식 시그니처는 Id a -> (a -> Id b) -> Id b이며 이는 a -> (a -> b) -> b다시 간단한 함수 응용 프로그램 인. 그것이 Cont r a사소하게 동등하다는 것을 확인하면 Id a, 우리는이 경우에도 (>>=)단지 함수 응용 이라는 것을 추론 할 수 있습니다 .

물론 Cont r a모든 사람이 염소를 가지고있는 미친 거꾸로 된 세계이므로 실제로 발생하는 일은 두 개의 일시 중단 된 계산을 새로운 일시 중단 된 계산으로 연결하기 위해 혼란스러운 방식으로 일을 뒤섞는 것과 관련이 있습니다. 그러나 본질적으로 이상한 것은 없습니다. 의 위에! 인수에 함수를 적용하는 것, 함수 프로그래머의 또 다른 날.

---

다음은 피보나치입니다.

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

호출 스택이없는 시스템이 있다고 가정 해보십시오. 꼬리 재귀 만 허용합니다. fib그 컴퓨터에서 어떻게 실행 합니까? 기하 급수적 인 시간 대신 선형으로 작동하도록 함수를 쉽게 다시 작성할 수 있지만 약간의 통찰력이 필요하며 기계적이 아닙니다.

꼬리를 재귀 적으로 만드는 데 장애물은 두 번의 재귀 호출이있는 세 번째 줄입니다. 우리는 한 번만 호출 할 수 있으며 결과도 제공해야합니다. 여기에 연속이 입력됩니다.

fib (n-1)결과를 계산 한 후 수행해야 할 작업을 지정하는 함수가 될 추가 매개 변수 를 가져 와서 호출합니다 x. fib (n-2)물론 추가 될 것입니다. 따라서 계산 fib n하려면 fib (n-1)그 후에 계산 하고 result를 호출하면 x을 계산 fib (n-2)하고 그 후에 result를 호출하면 y을 반환 x+y합니다.

즉, 다음과 같이 말해야합니다.

다음 계산을 수행하는 방법 : " fib' n c= 계산 fib n하고 c결과에 적용 "?

대답은 다음을 수행하는 것입니다. "계산 fib (n-1)하고 d결과에 적용 ", 여기서는 d x"계산 fib (n-2)하고 e결과에 적용 "을 의미 하고 , 여기서는을 e y의미 c (x+y)합니다. 코드에서 :

fib' 0 c = c 0
fib' 1 c = c 1
fib' n c = fib' (n-1) d
           where d x = fib' (n-2) e
                 where e y = c (x+y)

마찬가지로 람다를 사용할 수 있습니다.

fib' 0 = \c -> c 0
fib' 1 = \c -> c 1
fib' n = \c -> fib' (n-1) $ \x ->
               fib' (n-2) $ \y ->
               c (x+y)

실제 피보나치를 얻으려면 ID를 사용하십시오 fib' n id.. 선 fib (n-1) $ ...이 결과 x를 다음 결과 로 전달 한다고 생각할 수 있습니다 .

마지막 세 줄은 do블록 냄새가납니다.

fib' 0 = return 0
fib' 1 = return 1
fib' n = do x <- fib' (n-1)
            y <- fib' (n-2)
            return (x+y)

monad 정의에 따라 newtypes까지 동일 Cont합니다. 차이점에 유의하십시오. 있다 \c ->대신, 처음에 x <- ...거기 ... $ \x ->하고 c대신 return.

factorial n = n * factorial (n-1)CPS를 사용하여 꼬리 재귀 스타일로 작성해보십시오 .

어떻게 >>=작동합니까? m >>= k다음과 같다

do a <- m
   t <- k a
   return t

같은 스타일의 번역 등을, 만들기와 같이 fib', 당신은 얻을

\c -> m $ \a ->
      k a $ \t ->
      c t

단순화 \t -> c t에c

m >>= k = \c -> m $ \a -> k a c

당신이 얻는 새로운 유형 추가

m >>= k  = Cont $ \c -> runCont m $ \a -> runCont (k a) c

which is on top of this page. It's complex, but if you know how to translate between do notation and direct use, you don't need to know exact definition of >>=! Continuation monad is much clearer if you look at do-blocks.

Monads and continuations

If you look at this usage of list monad...

do x <- [10, 20]
   y <- [3,5]
   return (x+y)

[10,20] >>= \x ->
  [3,5] >>= \y ->
    return (x+y)

([10,20] >>=) $ \x ->
  ([3,5] >>=) $ \y ->
    return (x+y)

that looks like continuation! In fact, (>>=) when you apply one argument has type (a -> m b) -> m b which is Cont (m b) a. See sigfpe's Mother of all monads for explanation. I'd regard that as a good continuation monad tutorial, though it wasn't probably meant as it.

Since continuations and monads are so strongly related in both directions, I think what applies to monads applies to continuations: only hard work will teach you them, and not reading some burrito metaphor or analogy.

---

EDIT: Article migrated to the link below.

I've written up a tutorial directly addressing this topic that I hope you will find useful. (It certainly helped cement my understanding!) It's a bit too long to fit comfortably in a Stack Overflow topic, so I've migrated it to the Haskell Wiki.

Please see: MonadCont under the hood

---

I think the easiest way to get a grip on the Cont monad is to understand how to use its constructor. I'm going to assume the following definition for now, although the realities of the transformers package are slightly different:

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

This gives:

Cont :: ((a -> r) -> r) -> Cont r a

so to build a value of type Cont r a, we need to give a function to Cont:

value = Cont $ \k -> ...

Now, k itself has type a -> r, and the body of the lambda needs to have type r. An obvious thing to do would be to apply k to a value of type a, and get a value of type r. We can do that, yes, but that's really only one of many things we can do. Remember that value need not be polymorphic in r, it might be of type Cont String Integer or something else concrete. So:

• We could apply k to several values of type a, and combine the results somehow.
• We could apply k to a value of type a, observe the result, and then decide to apply k to something else based on that.
• We could ignore k altogether and just produce a value of type r ourselves.

But what does all this mean? What does k end up being? Well, in a do-block, we might have something looking like this:

flip runCont id $ do
  v <- thing1
  thing2 v
  x <- Cont $ \k -> ...
  thing3 x
  thing4

Here's the fun part: we can, in our minds and somewhat informally, split the do-block in two at the occurrence of the Cont constructor, and think of the rest of the entire computation after it as a value in itself. But hold on, what it is depends on what x is, so it's really a function from a value x of type a to some result value:

restOfTheComputation x = do
  thing3 x
  thing4

In fact, this restOfTheComputation is roughly speaking what k ends up being. In other words, you call k with a value which becomes the result x of your Cont computation, the rest of the computation runs, and then the r produced winds its way back into your lambda as the result of the call to k. So:

• if you called k multiple times, the rest of the computation will get run multiple times, and the results may be combined however you wish.
• if you didn't call k at all, the rest of the entire computation will be skipped, and the enclosing runCont call will just give you back whatever value of type r you managed to synthesise. That is, unless some other part of the computation is calling you from their k, and messing about with the result...

If you're still with me at this point it should be easy to see this could be quite powerful. To make the point a little, let's implement some standard type classes.

instance Functor (Cont r) where
  fmap f (Cont c) = Cont $ \k -> ...

We're given a Cont value with bind result x of type a, and a function f :: a -> b, and we want to make a Cont value with bind result f x of type b. Well, to set the bind result, just call k...

  fmap f (Cont c) = Cont $ \k -> k (f ...

Wait, where do we get x from? Well, it's going to involve c, which we haven't used yet. Remember how c works: it gets given a function, and then calls that function with its bind result. We want to call our function with f applied to that bind result. So:

  fmap f (Cont c) = Cont $ \k -> c (\x -> k (f x))

Tada! Next up, Applicative:

instance Applicative (Cont r) where
  pure x = Cont $ \k -> ...

This one's simple. We want the bind result to be the x we get.

  pure x = Cont $ \k -> k x

Now, <*>:

  Cont cf <*> Cont cx = Cont $ \k -> ...

This a little trickier, but uses essentially the same ideas as in fmap: first get the function from the first Cont, by making a lambda for it to call:

  Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> ...

Then get the value x from the second, and make fn x the bind result:

  Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> cx (\x -> k (fn x)))

Monad is much the same, although requires runCont or a case or let to unpack the newtype.

This answer is already quite long, so I won't go into ContT (in short: it is exactly the same as Cont! The only difference is in the kind of the type constructor, the implementations of everything are identical) or callCC (a useful combinator that provides a convenient way to ignore k, implementing early exit from a sub-block).

For a simple and plausible application, try Edward Z. Yang's blog post implementing labelled break and continue in for loops.

참고URL : https://stackoverflow.com/questions/3322540/how-and-why-does-the-haskell-cont-monad-work