ヒープ使用Haskellのパーセク

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形式のmanyLengthを書き換えることができます。一定のヒープ領域に実行を行い

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機能：これはmanyAccum 機能と非常に似ています。ここで

はちょうど完全性についてコンストラクタです：

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 
    } 

私も 低レベルmkPT機能を使用して、非CPS'ed機能に直接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" 

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