Debian Codegraph @

tests/inputs/Combinators.idr

raw
1 -- https://github.com/ziman/lightyear/raw/master/Lightyear/Combinators.idr
2 -- --------------------------------------------------------- [ Combinators.idr ]
3 -- Module : Lightyear.Combinators
4 -- Description : Generic Combinators
5 --
6 -- This code is distributed under the BSD 2-clause license.
7 -- See the file LICENSE in the root directory for its full text.
8 -- --------------------------------------------------------------------- [ EOH ]
9 module Lightyear.Combinators
10
11 import Data.Vect
12
13 import Lightyear.Core
14
15 %access export
16
17 -- --------------------------------------------------------------- [ Operators ]
18 infixr 3 :::
19 private
20 (:::) : a -> List a -> List a
21 (:::) x xs = x :: xs
22
23 infixr 3 ::.
24 private
25 (::.) : a -> Vect n a -> Vect (S n) a
26 (::.) x xs = x :: xs
27
28 -- -------------------------------------------------- [ Any Token and No Token ]
29
30 ||| Parse a single arbitrary token. Returns the parsed token.
31 |||
32 ||| This parser will fail if and only if the input stream is empty.
33 anyToken : (Monad m, Stream tok str) => ParserT str m tok
34 anyToken = satisfy (const True) <?> "any token"
35
36 ||| Parse the end of input.
37 |||
38 ||| This parser will succeed if and only if the input stream is empty.
39 eof : (Monad m, Stream tok str) => ParserT str m ()
40 eof = requireFailure anyToken <?> "end of input"
41
42 -- ---------------------------------------------------- [ Multiple Expressions ]
43
44 ||| Run some parser as many times as possible, collecting a list of
45 ||| successes.
46 many : Monad m => ParserT str m a -> ParserT str m (List a)
47 many p = (pure (:::) <*> p <*>| many p) <|> pure List.Nil
48
49 ||| Run the specified parser precisely `n` times, returning a vector
50 ||| of successes.
51 ntimes : Monad m => (n : Nat)
52 -> ParserT str m a
53 -> ParserT str m (Vect n a)
54 ntimes Z p = pure Vect.Nil
55 ntimes (S n) p = [| p ::. ntimes n p |]
56
57 ||| Like `many`, but the parser must succeed at least once
58 some : Monad m => ParserT str m a -> ParserT str m (List a)
59 some p = [| p ::: many p |]
60
61 -- --------------------------------------------------- [ Separated Expressions ]
62
63 ||| Parse repeated instances of at least one `p`, separated by `s`,
64 ||| returning a list of successes.
65 |||
66 ||| @ p the parser for items
67 ||| @ s the parser for separators
68 sepBy1 : Monad m => (p : ParserT str m a)
69 -> (s : ParserT str m b)
70 -> ParserT str m (List a)
71 sepBy1 p s = [| p ::: many (s *> p) |]
72
73 ||| Parse zero or more `p`s, separated by `s`s, returning a list of
74 ||| successes.
75 |||
76 ||| @ p the parser for items
77 ||| @ s the parser for separators
78 sepBy : Monad m => (p : ParserT str m a)
79 -> (s : ParserT str m b)
80 -> ParserT str m (List a)
81 sepBy p s = (p `sepBy1` s) <|> pure List.Nil
82
83 ||| Parse precisely `n` `p`s, separated by `s`s, returning a vect of
84 ||| successes.
85 |||
86 ||| @ n how many to parse
87 ||| @ p the parser for items
88 ||| @ s the parser for separators
89 sepByN : Monad m => (n : Nat)
90 -> (p : ParserT str m a)
91 -> (s : ParserT str m b)
92 -> ParserT str m (Vect n a)
93 sepByN Z p s = pure Vect.Nil
94 sepByN (S n) p s = [| p ::. ntimes n (s *> p) |]
95
96 ||| Parse one or more `p`s, separated by `op`s. Return a value that is
97 ||| the left associative application of the functions returned by `op`.
98 |||
99 ||| @ p the parser
100 ||| @ op the parser for operators
101 chainl1 : Monad m => (p : ParserT str m a)
102 -> (op: ParserT str m (a -> a -> a))
103 -> ParserT str m a
104 chainl1 p op = p >>= rest
105 where rest a1 = (do f <- op
106 a2 <- p
107 rest (f a1 a2)) <|> pure a1
108
109 ||| Parse zero or more `p`s, separated by `op`s. Return a value that is
110 ||| the left associative application of the functions returned by `op`.
111 ||| Return `a` when there are zero occurences of `p`.
112 |||
113 ||| @ p the parser
114 ||| @ op the parser for operators
115 chainl : Monad m => (p : ParserT str m a)
116 -> (op : ParserT str m (a -> a -> a))
117 -> a
118 -> ParserT str m a
119 chainl p op a = (p `chainl1` op) <|> pure a
120
121 ||| Parse one or more `p`s, separated by `op`s. Return a value that is
122 ||| the right associative application of the functions returned by `op`.
123 |||
124 ||| @ p the parser
125 ||| @ op the parser for operators
126 chainr1 : Monad m => (p : ParserT str m a)
127 -> (op: ParserT str m (a -> a -> a))
128 -> ParserT str m a
129 chainr1 p op = p >>= rest
130 where rest a1 = (do f <- op
131 a2 <- p >>= rest
132 rest (f a1 a2)) <|> pure a1
133
134 ||| Parse zero or more `p`s, separated by `op`s. Return a value that is
135 ||| the right associative application of the functions returned by `op`.
136 ||| Return `a` when there are zero occurences of `p`.
137 |||
138 ||| @ p the parser
139 ||| @ op the parser for operators
140 chainr : Monad m => (p : ParserT str m a)
141 -> (op : ParserT str m (a -> a -> a))
142 -> a
143 -> ParserT str m a
144 chainr p op a = (p `chainr1` op) <|> pure a
145
146 ||| Alternate between matches of `p` and `s`, starting with `p`,
147 ||| returning a list of successes from both.
148 alternating : Monad m => (p : ParserT str m a)
149 -> (s : ParserT str m a)
150 -> ParserT str m (List a)
151 alternating p s = (pure (:::) <*> p <*>| alternating s p) <|> pure List.Nil
152
153 ||| Throw away the result from a parser
154 skip : Monad m => ParserT str m a -> ParserT str m ()
155 skip = map (const ())
156
157 ||| Attempt to parse `p`. If it succeeds, then return the value. If it
158 ||| fails, continue parsing.
159 opt : Monad m => (p : ParserT str m a) -> ParserT str m (Maybe a)
160 opt p = map Just p <|> pure Nothing
161
162 ||| Parse open, then p, then close. Returns the result of `p`.
163 |||
164 ||| @open The opening parser.
165 ||| @close The closing parser.
166 ||| @p The parser for the middle part.
167 between : Monad m => (open : ParserT str m a)
168 -> (close : ParserT str m a)
169 -> (p : ParserT str m b)
170 -> ParserT str m b
171 between open close p = open *> p <* close
172
173 -- The following names are inspired by the cut operator from Prolog
174
175 -- ---------------------------------------------------- [ Monad-like Operators ]
176
177 infixr 5 >!=
178 ||| Committing bind
179 (>!=) : Monad m => ParserT str m a
180 -> (a -> ParserT str m b)
181 -> ParserT str m b
182 x >!= f = x >>= commitTo . f
183
184 infixr 5 >!
185 ||| Committing sequencing
186 (>!) : Monad m => ParserT str m a
187 -> ParserT str m b
188 -> ParserT str m b
189 x >! y = x >>= \_ => commitTo y
190
191 -- ---------------------------------------------- [ Applicative-like Operators ]
192
193 infixl 2 <*!>
194 ||| Committing application
195 (<*!>) : Monad m => ParserT str m (a -> b)
196 -> ParserT str m a
197 -> ParserT str m b
198 f <*!> x = f <*> commitTo x
199
200 infixl 2 <*!
201 (<*!) : Monad m => ParserT str m a
202 -> ParserT str m b
203 -> ParserT str m a
204 x <*! y = x <* commitTo y
205
206 infixl 2 *!>
207 (*!>) : Monad m => ParserT str m a
208 -> ParserT str m b
209 -> ParserT str m b
210 x *!> y = x *> commitTo y
211
212 -- ---------------------------------------------------------- [ Lazy Operators ]
213
214 infixl 2 <*|
215 (<*|) : Monad m => ParserT str m a
216 -> Lazy (ParserT str m b)
217 -> ParserT str m a
218 x <*| y = pure const <*> x <*>| y
219
220 infixl 2 *>|
221 (*>|) : Monad m => ParserT str m a
222 -> Lazy (ParserT str m b)
223 -> ParserT str m b
224 x *>| y = pure (const id) <*> x <*>| y
225 -- ---------------------------------------------------------------------- [ EF ]