| 1 |
{-| Element-agnostic parsing utilities for @pipes@ |
| 2 |
|
| 3 |
See "Pipes.Parse.Tutorial" for an extended tutorial |
| 4 |
-} |
| 5 |
|
| 6 |
{-# LANGUAGE RankNTypes #-} |
| 7 |
|
| 8 |
module Pipes.Parse ( |
| 9 |
-- * Parsing |
| 10 |
-- $parsing |
| 11 |
Parser |
| 12 |
, draw |
| 13 |
, skip |
| 14 |
, drawAll |
| 15 |
, skipAll |
| 16 |
, unDraw |
| 17 |
, peek |
| 18 |
, isEndOfInput |
| 19 |
, foldAll |
| 20 |
, foldAllM |
| 21 |
|
| 22 |
-- * Parsing Lenses |
| 23 |
-- $parsinglenses |
| 24 |
, span |
| 25 |
, splitAt |
| 26 |
, groupBy |
| 27 |
, group |
| 28 |
|
| 29 |
-- * Utilities |
| 30 |
, toParser |
| 31 |
, toParser_ |
| 32 |
, parsed |
| 33 |
, parsed_ |
| 34 |
, parseForever |
| 35 |
, parseForever_ |
| 36 |
|
| 37 |
-- * Re-exports |
| 38 |
-- $reexports |
| 39 |
, module Control.Monad.Trans.Class |
| 40 |
, module Control.Monad.Trans.State.Strict |
| 41 |
, module Pipes |
| 42 |
) where |
| 43 |
|
| 44 |
import Control.Monad (join, forever, liftM) |
| 45 |
import Control.Monad.Trans.Class (lift) |
| 46 |
import qualified Control.Monad.Trans.State.Strict as S |
| 47 |
import Control.Monad.Trans.State.Strict ( |
| 48 |
StateT(StateT, runStateT), evalStateT, execStateT ) |
| 49 |
import Data.Functor.Constant (Constant(Constant, getConstant)) |
| 50 |
import Data.Foldable (forM_) |
| 51 |
import Pipes.Internal (unsafeHoist, closed) |
| 52 |
import Pipes (Producer, yield, next) |
| 53 |
import Pipes as NoReexport |
| 54 |
|
| 55 |
import Prelude hiding (span, splitAt) |
| 56 |
|
| 57 |
{- $parsing |
| 58 |
@pipes-parse@ handles end-of-input and pushback by storing a 'Producer' in |
| 59 |
a 'StateT' layer. |
| 60 |
|
| 61 |
Connect 'Parser's to 'Producer's using either 'runStateT', 'evalStateT', or |
| 62 |
'execStateT': |
| 63 |
|
| 64 |
> runStateT :: Parser a m r -> Producer a m x -> m (r, Producer a m x) |
| 65 |
> evalStateT :: Parser a m r -> Producer a m x -> m r |
| 66 |
> execStateT :: Parser a m r -> Producer a m x -> m (Producer a m x) |
| 67 |
> ^^^^^^^^^^^^^^ |
| 68 |
> Leftovers |
| 69 |
-} |
| 70 |
|
| 71 |
-- | A 'Parser' is an action that reads from and writes to a stored 'Producer' |
| 72 |
type Parser a m r = forall x . StateT (Producer a m x) m r |
| 73 |
|
| 74 |
{-| Draw one element from the underlying 'Producer', returning 'Nothing' if the |
| 75 |
'Producer' is empty |
| 76 |
-} |
| 77 |
draw :: Monad m => Parser a m (Maybe a) |
| 78 |
draw = do |
| 79 |
p <- S.get |
| 80 |
x <- lift (next p) |
| 81 |
case x of |
| 82 |
Left r -> do |
| 83 |
S.put (return r) |
| 84 |
return Nothing |
| 85 |
Right (a, p') -> do |
| 86 |
S.put p' |
| 87 |
return (Just a) |
| 88 |
{-# INLINABLE draw #-} |
| 89 |
|
| 90 |
{-| Skip one element from the underlying 'Producer', returning 'True' if |
| 91 |
successful or 'False' if the 'Producer' is empty |
| 92 |
|
| 93 |
> skip = fmap isJust draw |
| 94 |
-} |
| 95 |
skip :: Monad m => Parser a m Bool |
| 96 |
skip = do |
| 97 |
x <- draw |
| 98 |
return $ case x of |
| 99 |
Nothing -> False |
| 100 |
Just _ -> True |
| 101 |
{-# INLINABLE skip #-} |
| 102 |
|
| 103 |
{-| Draw all elements from the underlying 'Producer' |
| 104 |
|
| 105 |
Note that 'drawAll' is not an idiomatic use of @pipes-parse@, but I provide |
| 106 |
it for simple testing purposes. Idiomatic @pipes-parse@ style consumes the |
| 107 |
elements immediately as they are generated instead of loading all elements |
| 108 |
into memory. For example, you can use 'foldAll' or 'foldAllM' for this |
| 109 |
purpose. |
| 110 |
-} |
| 111 |
drawAll :: Monad m => Parser a m [a] |
| 112 |
drawAll = go id |
| 113 |
where |
| 114 |
go diffAs = do |
| 115 |
x <- draw |
| 116 |
case x of |
| 117 |
Nothing -> return (diffAs []) |
| 118 |
Just a -> go (diffAs . (a:)) |
| 119 |
{-# INLINABLE drawAll #-} |
| 120 |
|
| 121 |
-- | Drain all elements from the underlying 'Producer' |
| 122 |
skipAll :: Monad m => Parser a m () |
| 123 |
skipAll = go |
| 124 |
where |
| 125 |
go = do |
| 126 |
x <- draw |
| 127 |
case x of |
| 128 |
Nothing -> return () |
| 129 |
Just _ -> go |
| 130 |
{-# INLINABLE skipAll #-} |
| 131 |
|
| 132 |
-- | Push back an element onto the underlying 'Producer' |
| 133 |
unDraw :: Monad m => a -> Parser a m () |
| 134 |
unDraw a = S.modify (yield a >>) |
| 135 |
{-# INLINABLE unDraw #-} |
| 136 |
|
| 137 |
{-| 'peek' checks the first element of the stream, but uses 'unDraw' to push the |
| 138 |
element back so that it is available for the next 'draw' command. |
| 139 |
|
| 140 |
> peek = do |
| 141 |
> x <- draw |
| 142 |
> case x of |
| 143 |
> Nothing -> return () |
| 144 |
> Just a -> unDraw a |
| 145 |
> return x |
| 146 |
-} |
| 147 |
peek :: Monad m => Parser a m (Maybe a) |
| 148 |
peek = do |
| 149 |
x <- draw |
| 150 |
forM_ x $ \a -> unDraw a |
| 151 |
return x |
| 152 |
{-# INLINABLE peek #-} |
| 153 |
|
| 154 |
{-| Check if the underlying 'Producer' is empty |
| 155 |
|
| 156 |
> isEndOfInput = fmap isNothing peek |
| 157 |
-} |
| 158 |
isEndOfInput :: Monad m => Parser a m Bool |
| 159 |
isEndOfInput = do |
| 160 |
x <- peek |
| 161 |
return (case x of |
| 162 |
Nothing -> True |
| 163 |
Just _ -> False ) |
| 164 |
{-# INLINABLE isEndOfInput #-} |
| 165 |
|
| 166 |
{-| Fold all input values |
| 167 |
|
| 168 |
> Control.Foldl.purely foldAll :: Monad m => Fold a b -> Parser a m b |
| 169 |
-} |
| 170 |
foldAll |
| 171 |
:: Monad m |
| 172 |
=> (x -> a -> x) |
| 173 |
-- ^ Step function |
| 174 |
-> x |
| 175 |
-- ^ Initial accumulator |
| 176 |
-> (x -> b) |
| 177 |
-- ^ Extraction function |
| 178 |
-> Parser a m b |
| 179 |
foldAll step begin done = go begin |
| 180 |
where |
| 181 |
go x = do |
| 182 |
ea <- draw |
| 183 |
case ea of |
| 184 |
Nothing -> return (done x) |
| 185 |
Just a -> go $! step x a |
| 186 |
{-# INLINABLE foldAll #-} |
| 187 |
|
| 188 |
{-| Fold all input values monadically |
| 189 |
|
| 190 |
> Control.Foldl.impurely foldAllM :: Monad m => FoldM a m b -> Parser a m b |
| 191 |
-} |
| 192 |
foldAllM |
| 193 |
:: Monad m |
| 194 |
=> (x -> a -> m x) |
| 195 |
-- ^ Step function |
| 196 |
-> m x |
| 197 |
-- ^ Initial accumulator |
| 198 |
-> (x -> m b) |
| 199 |
-- ^ Extraction function |
| 200 |
-> Parser a m b |
| 201 |
foldAllM step begin done = do |
| 202 |
x0 <- lift begin |
| 203 |
go x0 |
| 204 |
where |
| 205 |
go x = do |
| 206 |
ea <- draw |
| 207 |
case ea of |
| 208 |
Nothing -> lift (done x) |
| 209 |
Just a -> do |
| 210 |
x' <- lift (step x a) |
| 211 |
go $! x' |
| 212 |
{-# INLINABLE foldAllM #-} |
| 213 |
|
| 214 |
{- $parsinglenses |
| 215 |
Connect lenses to 'Producer's using ('Lens.Family.^.') or |
| 216 |
'Lens.Family.view': |
| 217 |
|
| 218 |
> (^.) :: Producer a m x |
| 219 |
> -> Lens' (Producer a m x) (Producer b m y) |
| 220 |
> -> Producer b m y |
| 221 |
|
| 222 |
Connect lenses to 'Parser's using 'Lens.Family.State.Strict.zoom': |
| 223 |
|
| 224 |
> zoom :: Lens' (Producer a m x) (Producer b m y) |
| 225 |
> -> Parser b m r |
| 226 |
> -> Parser a m r |
| 227 |
|
| 228 |
Connect lenses to each other using ('.') (i.e. function composition): |
| 229 |
|
| 230 |
> (.) :: Lens' (Producer a m x) (Producer b m y) |
| 231 |
> -> Lens' (Producer b m y) (Producer c m z) |
| 232 |
> -> Lens' (Producer a m y) (Producer c m z) |
| 233 |
-} |
| 234 |
|
| 235 |
type Lens' a b = forall f . (Functor f) => (b -> f b) -> a -> f a |
| 236 |
|
| 237 |
{-| 'span' is an improper lens that splits the 'Producer' into two 'Producer's, |
| 238 |
where the outer 'Producer' is the longest consecutive group of elements that |
| 239 |
satisfy the predicate |
| 240 |
-} |
| 241 |
span |
| 242 |
:: Monad m |
| 243 |
=> (a -> Bool) -> Lens' (Producer a m x) (Producer a m (Producer a m x)) |
| 244 |
span predicate k p0 = fmap join (k (to p0)) |
| 245 |
where |
| 246 |
-- to :: Monad m => Producer a m x -> Producer a m (Producer a m x) |
| 247 |
to p = do |
| 248 |
x <- lift (next p) |
| 249 |
case x of |
| 250 |
Left r -> return (return r) |
| 251 |
Right (a, p') -> |
| 252 |
if predicate a |
| 253 |
then do |
| 254 |
yield a |
| 255 |
to p' |
| 256 |
else return (yield a >> p') |
| 257 |
{-# INLINABLE span #-} |
| 258 |
|
| 259 |
{-| 'splitAt' is an improper lens that splits a 'Producer' into two 'Producer's |
| 260 |
after a fixed number of elements |
| 261 |
-} |
| 262 |
splitAt |
| 263 |
:: Monad m |
| 264 |
=> Int -> Lens' (Producer a m x) (Producer a m (Producer a m x)) |
| 265 |
splitAt n0 k p0 = fmap join (k (to n0 p0)) |
| 266 |
where |
| 267 |
-- to :: Monad m => Int -> Producer a m x -> Producer a m (Producer a m x) |
| 268 |
to n p = |
| 269 |
if n <= 0 |
| 270 |
then return p |
| 271 |
else do |
| 272 |
x <- lift (next p) |
| 273 |
case x of |
| 274 |
Left r -> return (return r) |
| 275 |
Right (a, p') -> do |
| 276 |
yield a |
| 277 |
to (n - 1) p' |
| 278 |
{-# INLINABLE splitAt #-} |
| 279 |
|
| 280 |
(^.) :: a -> ((b -> Constant b b) -> a -> Constant b a) -> b |
| 281 |
a ^. lens = getConstant (lens Constant a) |
| 282 |
|
| 283 |
{-| 'groupBy' splits a 'Producer' into two 'Producer's after the first group of |
| 284 |
elements that are equal according to the equality predicate |
| 285 |
-} |
| 286 |
groupBy |
| 287 |
:: Monad m |
| 288 |
=> (a -> a -> Bool) |
| 289 |
-> Lens' (Producer a m x) (Producer a m (Producer a m x)) |
| 290 |
groupBy equals k p0 = fmap join (k (to p0)) |
| 291 |
where |
| 292 |
-- to :: Monad m => Producer a m r -> Producer a m (Producer a m x) |
| 293 |
to p = do |
| 294 |
x <- lift (next p) |
| 295 |
case x of |
| 296 |
Left r -> return (return r) |
| 297 |
Right (a, p') -> (yield a >> p') ^. span (equals a) |
| 298 |
{-# INLINABLE groupBy #-} |
| 299 |
|
| 300 |
-- | Like 'groupBy', where the equality predicate is ('==') |
| 301 |
group |
| 302 |
:: (Monad m, Eq a) => Lens' (Producer a m x) (Producer a m (Producer a m x)) |
| 303 |
group = groupBy (==) |
| 304 |
{-# INLINABLE group #-} |
| 305 |
|
| 306 |
{-| Convert a 'Consumer' to a 'Parser' |
| 307 |
|
| 308 |
'Nothing' signifies end of input |
| 309 |
-} |
| 310 |
toParser :: Monad m => Consumer (Maybe a) m r -> Parser a m r |
| 311 |
toParser consumer = runEffect (lift draw >~ unsafeHoist lift consumer) |
| 312 |
{-# INLINABLE toParser #-} |
| 313 |
|
| 314 |
-- | Convert a never-ending 'Consumer' to a 'Parser' |
| 315 |
toParser_ :: Monad m => Consumer a m X -> Parser a m () |
| 316 |
toParser_ consumer = StateT $ \producer -> do |
| 317 |
r <- runEffect (producer >-> fmap closed consumer) |
| 318 |
return ((), return r) |
| 319 |
{-# INLINABLE toParser_ #-} |
| 320 |
|
| 321 |
|
| 322 |
{-| Run a `Parser` repeatedly on a `Producer`, `yield`ing each `Right result |
| 323 |
|
| 324 |
Returns the remainder of the `Producer` when the `Parser` returns `Left` |
| 325 |
-} |
| 326 |
parsed |
| 327 |
:: Monad m |
| 328 |
=> Parser a m (Either e b) |
| 329 |
-> Producer a m r -> Producer b m (e, Producer a m r) |
| 330 |
parsed parser = go |
| 331 |
where |
| 332 |
go p = do |
| 333 |
(x, p') <- lift (runStateT parser p) |
| 334 |
case x of |
| 335 |
Left r -> return (r, p') |
| 336 |
Right b -> do |
| 337 |
yield b |
| 338 |
go p' |
| 339 |
{-# INLINABLE parsed #-} |
| 340 |
|
| 341 |
{-| Run a `Parser` repeatedly on a `Producer`, `yield`ing each `Just` result |
| 342 |
|
| 343 |
Returns the remainder of the `Producer` when the `Parser` returns `Nothing` |
| 344 |
-} |
| 345 |
parsed_ |
| 346 |
:: Monad m |
| 347 |
=> Parser a m (Maybe b) |
| 348 |
-> Producer a m r |
| 349 |
-> Producer b m (Producer a m r) |
| 350 |
parsed_ parser p = do |
| 351 |
((), p') <- parsed parser' p |
| 352 |
return p' |
| 353 |
where |
| 354 |
parser' = do |
| 355 |
x <- parser |
| 356 |
return (case x of |
| 357 |
Nothing -> Left () |
| 358 |
Just b -> Right b ) |
| 359 |
{-# INLINABLE parsed_ #-} |
| 360 |
|
| 361 |
-- | Convert a 'Parser' to a 'Pipe' by running it repeatedly on the input |
| 362 |
parseForever :: |
| 363 |
Monad m => |
| 364 |
(forall n. Monad n => Parser a n (Either r b)) -> |
| 365 |
Pipe a b m r |
| 366 |
parseForever parse = go (forever (lift await >>= yield)) |
| 367 |
where go prod = do (b, prod') <- runStateT parse prod |
| 368 |
either return ((>> go prod') . yield) b |
| 369 |
{-# DEPRECATED parseForever "Use `parsed` instead" #-} |
| 370 |
|
| 371 |
-- | Variant of `parseForever` for parsers which return a Maybe |
| 372 |
-- instead of an Either |
| 373 |
parseForever_ :: |
| 374 |
Monad m => |
| 375 |
(forall n. Monad n => Parser a n (Maybe b)) -> |
| 376 |
Pipe a b m () |
| 377 |
parseForever_ parse = parseForever (liftM (maybe (Left ()) Right) parse) |
| 378 |
{-# DEPRECATED parseForever_ "Use `parsed_` instead" #-} |
| 379 |
|
| 380 |
{- $reexports |
| 381 |
"Control.Monad.Trans.Class" re-exports 'lift'. |
| 382 |
|
| 383 |
"Control.Monad.Trans.State.Strict" re-exports 'StateT', 'runStateT', |
| 384 |
'evalStateT', and 'execStateT'. |
| 385 |
|
| 386 |
"Pipes" re-exports 'Producer', 'yield', and 'next'. |
| 387 |
-} |