2876

pending completion

Build # 2876

Build Type

Pull #588

travis-ci-com

Committed by

web-flow

Commit Message

<a href="https://github.com/composewell/streamly/commit/<a class=hub.com/composewell/streamly/commit/215d1f0480bae1c74b4c80c4f7d862214f16069c">215d1f048<a href="https://github.com/composewell/streamly/commit/215d1f0480bae1c74b4c80c4f7d862214f16069c">">Merge </a><a class="double-link" href="https://github.com/composewell/streamly/commit/<a class="double-link" href="https://github.com/composewell/streamly/commit/03f05ed340148980e976bcf5d3543edb6225164b">03f05ed34</a>">03f05ed34</a><a href="https://github.com/composewell/streamly/commit/215d1f0480bae1c74b4c80c4f7d862214f16069c"> into 4933d37ed">4933d37ed</a>

Pull Request Pull Request #588: Updated type signature of `concatMapWith` to remove explicit forall.

Run Details

1 of 1 new or added line in 1 file covered. (100.0%)

3329 of 9291 relevant lines covered (35.83%)

0.36 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

5.26

/src/Streamly/Internal/Data/Parser/ParserK/Types.hs

#include "inline.hs"

-- |
-- Module      : Streamly.Internal.Data.Parser.ParserK.Types
-- Copyright   : (c) 2020 Composewell Technologies
-- License     : BSD-3-Clause
-- Maintainer  : streamly@composewell.com
-- Stability   : experimental
-- Portability : GHC
--
-- CPS style implementation of parsers.
--
-- The CPS representation allows linear performance for Applicative, sequenceA,
-- Monad, sequence, and Alternative, choice operations compared to the
-- quadratic complexity of the corresponding direct style operations. However,
-- direct style operations allow fusion with ~10x better performance than CPS.
--
-- The direct style representation does not allow for recursive definitions of
-- "some" and "many" whereas CPS allows that.

module Streamly.Internal.Data.Parser.ParserK.Types
    (
      Parser (..)
    , yield
    , die
    )
where

import Control.Monad (MonadPlus(..), ap)
import Control.Applicative (Alternative(..))
import Streamly.Internal.Data.Zipper (Zipper)
import qualified Streamly.Internal.Data.Zipper as Z

#if MIN_VERSION_base(4,9,0)
import qualified Control.Monad.Fail as Fail
#endif

newtype Parser m a b =
    MkParser { runParser :: forall r.
        Zipper m a -> ((Zipper m a, Either String b) -> m r) -> m r }

-- | Maps a function over the output of the fold.
--
instance Functor m => Functor (Parser m a) where
    {-# INLINE fmap #-}
    fmap f parser =
        MkParser $ \inp yieldk -> runParser parser inp (yieldk . fmap (fmap f))

-- | See 'Streamly.Internal.Data.Parser.yield'.
--
-- /Internal/
--
{-# INLINE yield #-}
yield :: b -> Parser m a b
yield b = MkParser (\inp yieldk -> yieldk (inp, Right b))

-------------------------------------------------------------------------------
-- Sequential applicative
-------------------------------------------------------------------------------

-- | 'Applicative' form of 'Streamly.Internal.Data.Parser.splitWith'. Note that
-- this operation does not fuse, use 'Streamly.Internal.Data.Parser.splitWith'
-- when fusion is important.
--
instance Monad m => Applicative (Parser m a) where
    {-# INLINE pure #-}
    pure = yield

    {-# INLINE (<*>) #-}
    (<*>) = ap

    {-# INLINE (*>) #-}
    m1 *> m2 = MkParser $ \inp yieldk ->
        let yield1 (z, b) = case b of
                Right _ -> runParser m2 z yieldk
                Left err -> runParser (die err) z yieldk
        in runParser m1 inp yield1

    {-# INLINE (<*) #-}
    m1 <* m2 = MkParser $ \inp yieldk ->
        let yield1 (z, b) = case b of
                Right _ -> runParser m2 z (\(z1, _) -> yieldk (z1, b))
                Left err -> runParser (die err) z yieldk
        in runParser m1 inp yield1

-- | See 'Streamly.Internal.Data.Parser.die'.
--
-- /Internal/
--
{-# INLINE die #-}
die :: String -> Parser m a b
die err = MkParser (\z yieldk -> yieldk (z, Left err))

-- | Monad composition can be used for lookbehind parsers, we can make the
-- future parses depend on the previously parsed values.
--
-- If we have to parse "a9" or "9a" but not "99" or "aa" we can use the
-- following parser:
--
-- @
-- backtracking :: MonadCatch m => PR.Parser m Char String
-- backtracking =
--     sequence [PR.satisfy isDigit, PR.satisfy isAlpha]
--     '<|>'
--     sequence [PR.satisfy isAlpha, PR.satisfy isDigit]
-- @
--
-- We know that if the first parse resulted in a digit at the first place then
-- the second parse is going to fail.  However, we waste that information and
-- parse the first character again in the second parse only to know that it is
-- not an alphabetic char.  By using lookbehind in a 'Monad' composition we can
-- avoid redundant work:
--
-- @
-- data DigitOrAlpha = Digit Char | Alpha Char
--
-- lookbehind :: MonadCatch m => PR.Parser m Char String
-- lookbehind = do
--     x1 \<-    Digit '<$>' PR.satisfy isDigit
--          '<|>' Alpha '<$>' PR.satisfy isAlpha
--
--     -- Note: the parse depends on what we parsed already
--     x2 <- case x1 of
--         Digit _ -> PR.satisfy isAlpha
--         Alpha _ -> PR.satisfy isDigit
--
--     return $ case x1 of
--         Digit x -> [x,x2]
--         Alpha x -> [x,x2]
-- @
--
-- See also 'Streamly.Internal.Data.Parser.concatMap'. This monad instance
-- does not fuse, use 'Streamly.Internal.Data.Parser.concatMap' when you need
-- fusion.
--
instance Monad m => Monad (Parser m a) where
    {-# INLINE return #-}
    return = pure

    {-# INLINE (>>=) #-}
    m >>= k = MkParser $ \inp yieldk ->
        let yield1 (z, b) = case b of
                Right x -> runParser (k x) z yieldk
                Left err -> runParser (die err) z yieldk
        in runParser m inp yield1

#if !(MIN_VERSION_base(4,13,0))
    -- This is redefined instead of just being Fail.fail to be
    -- compatible with base 4.8.
    {-# INLINE fail #-}
    fail = die
#endif

#if MIN_VERSION_base(4,9,0)
instance Monad m => Fail.MonadFail (Parser m a) where
    {-# INLINE fail #-}
    fail = die
#endif

-- | 'Alternative' form of 'Streamly.Internal.Data.Parser.alt'. Backtrack and
-- run the second parser if the first one fails.
--
-- The "some" and "many" operations of alternative accumulate results in a pure
-- list which is not scalable and streaming. Instead use
-- 'Streamly.Internal.Data.Parser.some' and
-- 'Streamly.Internal.Data.Parser.many' for fusible operations with composable
-- accumulation of results.
--
-- See also 'Streamly.Internal.Data.Parser.alt'. This 'Alternative' instance
-- does not fuse, use 'Streamly.Internal.Data.Parser.alt' when you need
-- fusion.
--
instance Monad m => Alternative (Parser m a) where
    {-# INLINE empty #-}
    empty = die "empty"

    {-# INLINE (<|>) #-}
    m1 <|> m2 = MkParser $ \inp yieldk ->
        let yield1 (z, b) = case b of
                Right _ -> yieldk (Z.release z, b)
                Left _ -> runParser m2 (Z.restore z) yieldk
        in runParser m1 (Z.checkpoint inp) yield1

    -- some and many are implemented here instead of using default definitions
    -- so that we can use INLINE on them. It gives 50% performance improvement.

    {-# INLINE many #-}
    many v = many_v

        where

        many_v = some_v <|> pure []
        some_v = (:) <$> v <*> many_v

    {-# INLINE some #-}
    some v = some_v

        where

        many_v = some_v <|> pure []
        some_v = (:) <$> v <*> many_v

-- | 'mzero' is same as 'empty', it aborts the parser. 'mplus' is same as
-- '<|>', it selects the first succeeding parser.
--
-- /Internal/
--
instance Monad m => MonadPlus (Parser m a) where
    {-# INLINE mzero #-}
    mzero = die "mzero"

    {-# INLINE mplus #-}
    mplus = (<|>)

1	#include "inline.hs"
2
3	-- \|
4	-- Module : Streamly.Internal.Data.Parser.ParserK.Types
5	-- Copyright : (c) 2020 Composewell Technologies
6	-- License : BSD-3-Clause
7	-- Maintainer : streamly@composewell.com
8	-- Stability : experimental
9	-- Portability : GHC
10	--
11	-- CPS style implementation of parsers.
12	--
13	-- The CPS representation allows linear performance for Applicative, sequenceA,
14	-- Monad, sequence, and Alternative, choice operations compared to the
15	-- quadratic complexity of the corresponding direct style operations. However,
16	-- direct style operations allow fusion with ~10x better performance than CPS.
17	--
18	-- The direct style representation does not allow for recursive definitions of
19	-- "some" and "many" whereas CPS allows that.
20
21	module Streamly.Internal.Data.Parser.ParserK.Types
22	(
23	Parser (..)
24	, yield
25	, die
26	)
27	where
28
29	import Control.Monad (MonadPlus(..), ap)
30	import Control.Applicative (Alternative(..))
31	import Streamly.Internal.Data.Zipper (Zipper)
32	import qualified Streamly.Internal.Data.Zipper as Z
33
34	#if MIN_VERSION_base(4,9,0)
35	import qualified Control.Monad.Fail as Fail
36	#endif
37
38	newtype Parser m a b =
39	MkParser { runParser :: forall r.	1✔
40	Zipper m a -> ((Zipper m a, Either String b) -> m r) -> m r }
41
42	-- \| Maps a function over the output of the fold.
43	--
44	instance Functor m => Functor (Parser m a) where
45	{-# INLINE fmap #-}
46	fmap f parser =	×
47	MkParser $ \inp yieldk -> runParser parser inp (yieldk . fmap (fmap f))	×
48
49	-- \| See 'Streamly.Internal.Data.Parser.yield'.
50	--
51	-- /Internal/
52	--
53	{-# INLINE yield #-}
54	yield :: b -> Parser m a b
55	yield b = MkParser (\inp yieldk -> yieldk (inp, Right b))	×
56
57	-------------------------------------------------------------------------------
58	-- Sequential applicative
59	-------------------------------------------------------------------------------
60
61	-- \| 'Applicative' form of 'Streamly.Internal.Data.Parser.splitWith'. Note that
62	-- this operation does not fuse, use 'Streamly.Internal.Data.Parser.splitWith'
63	-- when fusion is important.
64	--
65	instance Monad m => Applicative (Parser m a) where
66	{-# INLINE pure #-}
67	pure = yield	×
68
69	{-# INLINE (<*>) #-}
70	(<*>) = ap	×
71
72	{-# INLINE (*>) #-}
73	m1 *> m2 = MkParser $ \inp yieldk ->	×
74	let yield1 (z, b) = case b of	×
75	Right _ -> runParser m2 z yieldk	×
76	Left err -> runParser (die err) z yieldk	×
77	in runParser m1 inp yield1	×
78
79	{-# INLINE (<*) #-}
80	m1 <* m2 = MkParser $ \inp yieldk ->	×
81	let yield1 (z, b) = case b of	×
82	Right _ -> runParser m2 z (\(z1, _) -> yieldk (z1, b))	×
83	Left err -> runParser (die err) z yieldk	×
84	in runParser m1 inp yield1	×
85
86	-- \| See 'Streamly.Internal.Data.Parser.die'.
87	--
88	-- /Internal/
89	--
90	{-# INLINE die #-}
91	die :: String -> Parser m a b
92	die err = MkParser (\z yieldk -> yieldk (z, Left err))	×
93
94	-- \| Monad composition can be used for lookbehind parsers, we can make the
95	-- future parses depend on the previously parsed values.
96	--
97	-- If we have to parse "a9" or "9a" but not "99" or "aa" we can use the
98	-- following parser:
99	--
100	-- @
101	-- backtracking :: MonadCatch m => PR.Parser m Char String
102	-- backtracking =
103	-- sequence [PR.satisfy isDigit, PR.satisfy isAlpha]
104	-- '<\|>'
105	-- sequence [PR.satisfy isAlpha, PR.satisfy isDigit]
106	-- @
107	--
108	-- We know that if the first parse resulted in a digit at the first place then
109	-- the second parse is going to fail. However, we waste that information and
110	-- parse the first character again in the second parse only to know that it is
111	-- not an alphabetic char. By using lookbehind in a 'Monad' composition we can
112	-- avoid redundant work:
113	--
114	-- @
115	-- data DigitOrAlpha = Digit Char \| Alpha Char
116	--
117	-- lookbehind :: MonadCatch m => PR.Parser m Char String
118	-- lookbehind = do
119	-- x1 \<- Digit '<$>' PR.satisfy isDigit
120	-- '<\|>' Alpha '<$>' PR.satisfy isAlpha
121	--
122	-- -- Note: the parse depends on what we parsed already
123	-- x2 <- case x1 of
124	-- Digit _ -> PR.satisfy isAlpha
125	-- Alpha _ -> PR.satisfy isDigit
126	--
127	-- return $ case x1 of
128	-- Digit x -> [x,x2]
129	-- Alpha x -> [x,x2]
130	-- @
131	--
132	-- See also 'Streamly.Internal.Data.Parser.concatMap'. This monad instance
133	-- does not fuse, use 'Streamly.Internal.Data.Parser.concatMap' when you need
134	-- fusion.
135	--
136	instance Monad m => Monad (Parser m a) where
137	{-# INLINE return #-}
138	return = pure	×
139
140	{-# INLINE (>>=) #-}
141	m >>= k = MkParser $ \inp yieldk ->	×
142	let yield1 (z, b) = case b of	×
143	Right x -> runParser (k x) z yieldk	×
144	Left err -> runParser (die err) z yieldk	×
145	in runParser m inp yield1	×
146
147	#if !(MIN_VERSION_base(4,13,0))
148	-- This is redefined instead of just being Fail.fail to be
149	-- compatible with base 4.8.
150	{-# INLINE fail #-}
151	fail = die
152	#endif
153
154	#if MIN_VERSION_base(4,9,0)
155	instance Monad m => Fail.MonadFail (Parser m a) where
156	{-# INLINE fail #-}
157	fail = die	1✔
158	#endif
159
160	-- \| 'Alternative' form of 'Streamly.Internal.Data.Parser.alt'. Backtrack and
161	-- run the second parser if the first one fails.
162	--
163	-- The "some" and "many" operations of alternative accumulate results in a pure
164	-- list which is not scalable and streaming. Instead use
165	-- 'Streamly.Internal.Data.Parser.some' and
166	-- 'Streamly.Internal.Data.Parser.many' for fusible operations with composable
167	-- accumulation of results.
168	--
169	-- See also 'Streamly.Internal.Data.Parser.alt'. This 'Alternative' instance
170	-- does not fuse, use 'Streamly.Internal.Data.Parser.alt' when you need
171	-- fusion.
172	--
173	instance Monad m => Alternative (Parser m a) where
174	{-# INLINE empty #-}
175	empty = die "empty"	×
176
177	{-# INLINE (<\|>) #-}
178	m1 <\|> m2 = MkParser $ \inp yieldk ->	×
179	let yield1 (z, b) = case b of	×
180	Right _ -> yieldk (Z.release z, b)	×
181	Left _ -> runParser m2 (Z.restore z) yieldk	×
182	in runParser m1 (Z.checkpoint inp) yield1	×
183
184	-- some and many are implemented here instead of using default definitions
185	-- so that we can use INLINE on them. It gives 50% performance improvement.
186
187	{-# INLINE many #-}
188	many v = many_v	×
189
190	where
191
192	many_v = some_v <\|> pure []	×
193	some_v = (:) <$> v <*> many_v	×
194
195	{-# INLINE some #-}
196	some v = some_v	×
197
198	where
199
200	many_v = some_v <\|> pure []	×
201	some_v = (:) <$> v <*> many_v	×
202
203	-- \| 'mzero' is same as 'empty', it aborts the parser. 'mplus' is same as
204	-- '<\|>', it selects the first succeeding parser.
205	--
206	-- /Internal/
207	--
208	instance Monad m => MonadPlus (Parser m a) where
209	{-# INLINE mzero #-}
210	mzero = die "mzero"	×
211
212	{-# INLINE mplus #-}
213	mplus = (<\|>)	×

composewell / streamly / 2876

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous