А как называются парсеры, которые заранее (до запуска) знают, сколько

токенов (байт/символов) они потребят?

{-# LANGUAGE ApplicativeDo #-} {-# LANGUAGE GADTs #-} import Control.Applicative import Control.Monad.Except import Data.Foldable data Parser a where Fail :: String -> Parser a Empty :: Parser () Pure :: a -> Parser a Symbol :: Char -> Parser Char Map :: (a -> b) -> Parser a -> Parser b Product :: Parser a -> Parser b -> Parser (a, b) Either :: Parser a -> Parser a -> Parser a Fix :: (Parser a -> Parser a) -> Parser a instance Functor Parser where fmap = Map instance Applicative Parser where pure = Pure pf <*> px = Map (uncurry ($)) (Product pf px) instance Alternative Parser where (<|>) = Either empty = Fail "" string :: String -> Parser String string = traverse Symbol eof :: Parser () eof = Empty runParser :: String -> Parser a -> Except String (String, a) runParser _ (Fail e) = throwError e runParser "" Empty = pure ("", ()) runParser _ Empty = throwError "Expected eof" runParser s (Pure x) = pure (s, x) runParser (c : s) (Symbol c') | c == c' = pure (s, c) runParser _ (Symbol c') = throwError ("Expected " <> [c']) runParser s (Map f p) = (fmap . fmap) f (runParser s p) runParser s (Product a b) = do (s, a) <- runParser s a (s, b) <- runParser s b pure (s, (a, b)) runParser s (Either a b) = runParser s a <|> runParser s b runParser s (Fix f) = runParser s (f (Fix f)) data I = I Int (Maybe Int) prettyI :: I -> String prettyI (I a (Just b)) = "[" <> show a <> ", " <> show b <> "]" prettyI (I a Nothing) = "[" <> show a <> ", +∞]" zero, one, inf :: I zero = I 0 (Just 0) one = I 1 (Just 1) inf = I 0 Nothing plus, imax :: I -> I -> I plus (I x y) (I x' y') = I (x + x') (liftA2 (+) y y') imax (I x y) (I x' y') = I (min x x') (liftA2 max y y') -- Nothing if there are no success path len :: Parser a -> Maybe I len (Fail _) = Nothing len Empty = Just zero len (Pure _) = Just zero len (Symbol _) = Just one len (Map _ p) = len p len (Product a b) = liftA2 plus (len a) (len b) len (Either a b) = let (la, lb) = (len a, len b) in liftA2 imax la lb <|> la <|> lb len (Fix f) = Just inf qwe :: Parser Bool qwe = do _ <- string "bool=" b <- asum [True <$ string "true", False <$ string "false"] _ <- eof pure b main = do case len qwe of Nothing -> putStrLn "no success path" Just l -> putStrLn (prettyI l) print (runExcept (runParser "bool=true" qwe)) print (runExcept (runParser "bool=false" qwe)) print (runExcept (runParser "bool=false something" qwe)) print (runExcept (runParser "=false" qwe)) -- [9, 10] -- Right ("",True) -- Right ("",False) -- Left "Expected eof" -- Left "Expected b"

А len тут где используется?

чет запахло докладом нижника про стрелки... (ну тот, с хреновым звуком)

А есть ссылка?

ща

len (Fix f) = inf вот эту строчку можно наверное уточнить, если f (Fix f) там внутри себя Fix нигде не использует, то размер можно посчитать еще, а иначе inf так же можно добавить специальный Fix ограниченный, который может не больше N раз вызываться, тогда тоже можно посчитать максимальную длину (и опять же, если внутри Fix не используется, то даже не учитывая N можно)

Парсер тут это почти свободный профунктор?

Надо не забыть на свежую голову посмотреть

liftAlt2 f x y = f x y <|> x <|> y

можно это записать через фри{аппликатив,альтернатив}?

Да

покажи)

https://blog.jle.im/entry/free-alternative-regexp.html :D

ну тут еще всякие фиксы и туплы/суммы