힙 사용 하스켈의 파섹

Question

내가 parsec를 사용하여 다음 파서를 작성하려고 해요 :

manyLength 
    :: forall s u m a. 
    Monad m 
    => ParsecT s u m a -> ParsecT s u m Int 
manyLength p = go 0 
    where 
    go :: Int -> ParsecT s u m Int 
    go !i = (p *> go (i + 1)) <|> pure i 

이 대신 [a], 그것을 수익률을 반환의 many 기능처럼 횟수가 Parser a에 성공했습니다.

이 작동하지만 일정한 힙 공간에서 실행할 수 없습니다. 이것은 go에 대한 재귀 호출이 꼬리 호출 위치에 있지 않기 때문에 을 의미합니다.

parsec가 생성자를 ParsecT으로 내보낼 경우 을 CPS'ed 형식으로 다시 쓸 수 있습니다. 이것은 manyAccum 기능과 매우 유사합니다 :

manyLengthCPS :: forall s u m a. ParsecT s u m a -> ParsecT s u m Int 
manyLengthCPS p = ParsecT f 
    where 
    f 
     :: forall b. 
     State s u 
     -> (Int -> State s u -> ParseError -> m b) -- consumed ok 
     -> (ParseError -> m b)      -- consumed err 
     -> (Int -> State s u -> ParseError -> m b) -- empty ok 
     -> (ParseError -> m b)      -- empty err 
     -> m b 
    f s cok cerr eok _ = 
     let walk :: Int -> a -> State s u -> ParseError -> m b 
      walk !i _ s' _ = 
      unParser p s' 
       (walk $ i + 1)   -- consumed-ok 
       cerr      -- consumed-err 
       manyLengthCPSErr   -- empty-ok 
       (\e -> cok (i + 1) s' e) -- empty-err 
     in unParser p s (walk 0) cerr manyLengthCPSErr (\e -> eok 0 s e) 
    {-# INLINE f #-} 

manyLengthCPSErr :: Monad m => m a 
manyLengthCPSErr = 
    fail "manyLengthCPS can't be used on parser that accepts empty input" 

이 manyLengthCPS 기능 일정한 힙 공간에서 실행한다.

manyLengthLowLevel 
    :: forall s u m a. 
    Monad m 
    => ParsecT s u m a -> ParsecT s u m Int 
manyLengthLowLevel p = mkPT f 
    where 
    f :: State s u -> m (Consumed (m (Reply s u Int))) 
    f parseState = do 
     consumed <- runParsecT p parseState 
     case consumed of 
     Empty mReply -> do 
      reply <- mReply 
      case reply of 
      Ok _ _ _ -> manyLengthErr 
      Error parseErr -> pure . Empty . pure $ Ok 0 parseState parseErr 
     Consumed mReply -> do 
      reply <- mReply 
      case reply of 
      Ok a newState parseErr -> walk 0 a newState parseErr 
      Error parseErr -> pure . Consumed . pure $ Error parseErr 
     where 
     walk 
      :: Int 
      -> a 
      -> State s u 
      -> ParseError 
      -> m (Consumed (m (Reply s u Int))) 
     walk !i _ parseState' _ = do 
      consumed <- runParsecT p parseState' 
      case consumed of 
      Empty mReply -> do 
       reply <- mReply 
       case reply of 
       Ok _ _ _ -> manyLengthErr 
       Error parseErr -> 
        pure . Consumed . pure $ Ok (i + 1) parseState' parseErr 
      Consumed mReply -> do 
       reply <- mReply 
       case reply of 
       Ok a newState parseErr -> walk (i + 1) a newState parseErr 
       Error parseErr -> pure . Consumed . pure $ Error parseErr 

manyLengthErr :: Monad m => m a 
manyLengthErr = 
    fail "manyLengthLowLevel can't be used on parser that accepts empty input" 

: I은 또한 낮은 레벨 mkPT 기능 를 이용한 비 CPS'ed 기능에 직접 manyLengthCPS 좌회전 시도

newtype ParsecT s u m a = ParsecT 
    { unParser 
     :: forall b . 
     State s u 
     -> (a -> State s u -> ParseError -> m b) -- consumed ok 
     -> (ParseError -> m b)     -- consumed err 
     -> (a -> State s u -> ParseError -> m b) -- empty ok 
     -> (ParseError -> m b)     -- empty err 
     -> m b 
    } 

: 여기

은 완전성 대한 ParsecT 생성자

manyLength처럼 manyLengthLowLevel은 일정한 힙 공간에서 실행되지 않습니다.

---

심지어 CPS-스타일을 작성하지 않고 그래서 일정한 힙 공간에서 실행 manyLength을 쓸 수 있습니까? 그렇지 않다면 왜 안 되겠습니까? CPS 스타일은 가능하지만 CPS 스타일이 아닌 이유는 무엇입니까?

Answer 1

이것은 일정한 힙 공간에서 실행됩니다. 먼저 p을 시도하고 go을 실행할지 여부를 결정하기 위해 성공 결과에 대한 사례 분석을 명시 적으로 수행하여 go이 마무리 호출 위치에 도달하게하는 것입니다.

manyLength 
    :: Monad m 
    => ParsecT s u m a -> ParsecT s u m Int 
manyLength p = go 0 
    where 
    go :: Int -> ParsecT s u m Int 
    go !i = do 
     success <- (p *> pure True) <|> pure False 
     if success then go (i+1) else pure i