모나드 변압기에있는 기본 모던을 뒤돌아서

Question

부 프로젝트로 저는 Regex parser/compiler을 구현하고 있습니다.

나는 실제 일치하는 부분이 어떤 역 추적 모나드가 어떻게 작동 하는지를 배우기에 좋은 시간이라고 생각했다; 예를 들어리스트 모나드처럼. ListT 가브리엘의 List.Transformer lib

국가 모나드 부분에서입니다

data Expr 
    = Group Int Expr 
    | Terms [Expr] 
    | OneOf [Expr] 
    | Repetition Expr Int (Maybe Int) 
    | Empty 
    | BackRef Int 
    | Wildcard 
    | Atom Char 
    | Start 
    | End 
    deriving (Show) 

data RState = RState 
    { groups :: Groups 
    , leftover :: String 
    } deriving Show 

match :: Expr -> ListT (State RState) String 

캡처 된 그룹을 추적

(내가 사용할 수 있도록 :

나는 그렇게처럼 내 '일치'알고리즘을 구조화 결국 그것들은 역 참조에 매치 될 때) 그리고 남은 문자열은 소비하기 위해 남았습니다. Expr은 일종의 AST 인 Regex를 나타내는 데이터 구조입니다.

어쨌든; 이것은 잘 작동한다; 일치하는 항목이 있으면 다시 검색합니다. 결과가 일치하는 부분을 반환하고 이에 따라 나머지 항목과 그룹을 변경하면 비 결정적 방식으로 작동합니다. 이는 가능한 모든 이전 일치를 계속 사용하려고하기 때문에 종료됩니다. 정규 표현식의 다음 부분을 처리하려고합니다. 문제는 이전 결과에 대해서만 역 추적을하지만 이전 상태로는 되돌릴 수 없다는 것입니다. 그 결과 정규식에 선택적 항목의 사슬을 일치에 대한 내 alternative 일치하는 코드 (예 : | B * | C 각 부분은 '용어'이다) 다음과 같습니다

match (OneOf terms) = do 
    st <- get 
    -- Backtrack the state and try again on each alternative 
    let try t = put st >> match t 
    asum (try <$> terms) 

는 기본적으로 I가 일치하도록 시도 각 용어는 일치하지만 실패하더라도 여전히 상태를 변경합니다! 그래서 수동으로 실패 사이의 상태를 되 감을 필요가 있습니다. 이는 <|>의 ListT 구현하는 것입니다 : 우리가 기본 모나드를 실행하고 같은 맥락에서 계속 볼 수

ListT m <|> l = ListT (do 
    s <- m 
    case s of 
     Nil  -> next l 
     Cons x l' -> return (Cons x (l' <|> l))) 

.

내가이 비슷한 원하는 :

ListT m <|> l = ListT (do 
    st <- get 
    s <- m 
    case s of 
     Nil  -> put st >> next l 
     Cons x l' -> return (Cons x (l' <|> l))) 

...하지만 일반적으로 모든 모나드 효과; 이것이 가능한지 확실하지 않습니다.

나는 가능한 해결책으로 Logic Monad을 조사했지만, 종이를 읽은 후에도 내가 원하는 것을 할 수 있는지 여부를 알 수 없다. 어쩌면 ifte을 사용하는 것이 가능 할까?

모나드의 결과를 역 추적 할뿐만 아니라 모나드 계산을 역 추적하는 역 추적 모나드가 있습니까? IO와 같은 것은 불가능하다고 생각하지만 이론적으로 순수한 모나드는 가능해야합니까? 나는 그것이 일반적으로 가능하지 않다는 것을 의미하지만 내 경우에이 기능을 구현하기 위해 구현할 수있는 유형 클래스가 있습니까?

감사합니다. 나는 내가 이것을 크게 생각해 내도록 도와 줘서 고마워.

Answer 1

해결책은 @danidiaz가 제안한대로 스택을 반전하는 것입니다.

바깥 쪽 모나드 변압기가 내면 변압기를 사용한다는 사실을 기억하면 도움이됩니다. 그래서 SomeMonadT (State s)은 SomeMonadT이 무엇이든 관계없이 상태가 "단일 스레드"가됩니다.

조명 예제는 다른 모나드보다 StateT 모나드 변환기를 풀고 있습니다.의 우리가 있다고 가정 해 봅시다 :

foo :: StateT S M A 
bar :: StateT S M B 

do a <- foo 
    b <- bar 
    return (a,b) 

이 글을 쓰는 단지 멋진 방법입니다 : 패턴이 다른 모나드 컨텍스트 내에서 발생하는 점을 제외하고는 State 모나드 동기를 부여 익숙한 패턴이

foo :: S -> M (A, S) 
bar :: S -> M (B, S) 

\s1 -> do 
    (a,s2) <- foo s1 
    (b,s3) <- bar s2 
    return ((a,b),s3) 

합니다. 그 맥락은 왕이다. 변압기가 그것에 대해 할 수있는 것은 아무것도 없다. ListT (State s) 수단

는 하나s 상태를 추적 계산 된 다음에 의해 정의된다 ListT 위에 약간의 "설탕"가있다. stateful machine (단 하나의 상태를 추적 할 수있는 능력을 가짐)에서 비 결정론의 구현이라고 생각할 수 있습니다.

반면에 StateT s []은 본질적으로 비 결정적이며, 그 다음에는 상태를 에뮬레이션하는 "설탕"이 있습니다. 기본 시스템은 비 결정적 역 추적 시스템이며, 변압기는 코딩 패턴을 사용하여 해당 시스템의 상태를 시뮬레이트합니다.

이 조금 wishywashy하고 직관적 인 느낌 영토, 그래서 난이 도움이되었다 희망 : 여기

약간의 직관을 제공하는 데 도움이 댄 Piponi하여 diagram입니다.

추가 읽기 : How to design a monadic stack?