| 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 ] |