MonadRef를 사용하여 MonadCont 구현

MonadRef를 사용하여 MonadCont 구현

---

반환 유형에 유형을 사용할 수 없다는forallCont 잘 알려진 문제 가 있습니다 .

그러나 다음과 같은 정의는 괜찮습니다.

class Monad m => MonadCont' m where
    callCC' :: ((a -> forall b. m b) -> m a) -> m a
    shift :: (forall r.(a -> m r) -> m r) -> m a
    reset :: m a -> m a

그런 다음 의미있는 인스턴스를 찾습니다. 에서 본 논문 저자는 우리가 구현할 수 있다고 주장 MonadFix상단에 ContT r m있음을 제공하는 m구현 MonadFix및 MonadRef. 그러나 우리가 가지고 있다면 MonadRef실제로 callCC'다음과 같이 구현할 수 있다고 생각합니다 .

--satisfy law: mzero >>= f === mzero
class Monad m => MonadZero m where
    mzero :: m a

instance (MonadZero m, MonadRef r m) => MonadCont' m where
    callCC' k = do
        ref <- newRef Nothing
        v <- k (\a -> writeRef ref (Just a) >> mzero)
        r <- readRef ref
        return $ maybe v id r
    shift = ...
    reset = ...

(불행히도의 의미에 익숙하지 않은 오전 shift과 reset그 구현을 제공하지 않았다 나는 그렇게)

이 구현은 나에게 괜찮은 것 같습니다. 직관적 callCC'으로 호출 될 때 k자체 효과가 항상 실패하는 함수를 제공합니다 (임의의 값을 제공 할 수는 없지만 b항상 mzero유형을 제공 할 수 m b있으며 법에 따라 모든 것을 효과적으로 중지해야합니다). 효과가 계산 됨), 수신 된 값을의 최종 결과로 캡처합니다 callCC'.

그래서 제 질문은 :

이 구현이 이상에 대해 예상대로 작동 callCC합니까? 우리는 구현할 수 shift와 reset의미 적절한뿐만 아니라 함께?

위의 내용 외에도 알고 싶습니다.

적절한 동작을 보장하기 위해 우리는 MonadRef. 그렇다면 MonadRef위의 구현이 예상대로 작동하도록하기 위해 a 법칙은 무엇 입니까?

최신 정보

위의 순진한 구현으로는 충분하지 않습니다. "연속 전류"를 만족 시키려면

callCC $\k -> k m === callCC $ const m === m

구현을 조정해야합니다.

instance (MonadPlus m, MonadRef r m) => MonadCont' m where
    callCC' k = do 
       ref <- newRef mzero
       mplus (k $ \a -> writeRef ref (return a) >> mzero) (join (readRef ref))

즉, 원본으로 MonadZero는 충분하지 않으므로 mzero전체 계산을 취소하지 않고 값을 일반 계산과 결합 할 수 있어야합니다 .

위의 내용은 질문에 대한 답이 아니라 원래의 시도가 후보자로 위조 되었기 때문에 조정 된 것입니다. 그러나 업데이트 된 버전의 경우 원래 질문은 여전히 ​​질문입니다. 특히, reset그리고 shift여전히 구현할 수 있습니다.

---

(아직 답은 아니지만 몇 가지 단서 만 떠 올랐습니다. 이것이 나 자신이나 다른 사람의 진정한 답으로 이어지기를 바랍니다.)

Call-by-Value는 Call-by-Name과 이중입니다 -Philip Wadler

위 논문에서 저자는 고전적 논리에 해당하는 형식화 된 미적분 인 "이중 미적분"을 소개했습니다. 마지막 섹션에는 다음과 같은 세그먼트가 있습니다.

필요에 따라 호출에 이중화 된 전략은 처음 평가 될 때 공동 값을 공동 값으로 덮어 써서 이러한 비 효율성을 피할 수 있습니다.

Wadler의 논문에서 언급했듯이, 연속을 열심히 평가하는 이름 별 호출 (모든 값이 평가되기 전에 반환 됨)이면서 값별 호출은 연속을 느리게 평가합니다 (모든 값이 평가 된 후에 만 ​​반환 됨).

이제 callCC'위 의 내용을 살펴보면 이것이 연속 측면에서 필요에 따라 호출의 이중의 예라고 생각합니다. 평가 전략은 주어진 함수에 가짜 "연속"을 제공하지만 나중에 "참"연속을 호출하기 위해이 시점에서 상태를 캐시하는 것입니다. 이것은 어떻게 든 연속의 캐시를 만드는 것과 같으므로 계산이 완료되면 해당 연속을 복원합니다. 그러나 평가 된 값을 캐시하는 것은 필요에 따라 호출한다는 의미입니다.

일반적으로 상태 (현재 시점까지의 계산)는 연속 (미래 계산)과 이중이라고 생각합니다. 이것은 몇 가지 현상을 설명 할 것입니다. 이것이 사실이라면 MonadRef(글로벌 및 다형성 상태에 해당)가 MoncadCont(글로벌 및 다형성 연속에 해당 ) 이중 이므로 서로를 구현하는 데 사용할 수 있다는 것은 놀라운 일이 아닙니다 .

참고 URL : https://stackoverflow.com/questions/24237653/use-monadref-to-implement-monadcont