[Haskell-cafe] Frisby (PEG parser) unbiased-choice thoughts

[Isaac Dupree]

since I don't like unexpected behavior happening when something not 
intended to happen, happens, and it's better documentation (a free 
assertion)  -- I find myself making Haskell comments to specify whether 
the left-biasedness of each (//) is important, various places in my own 
code that uses frisby.  We examine how could such an operator could 
behave, having similar effect to (//) but symmetric (call it (=|=);
   (p1 =|= p2)  should be equivalent to  (p2 =|= p1)  )...

I will use original frisby syntax (see 
<http://repetae.net/john/computer/frisby/>), not the 
Applicative/Alternative instances I added, to be clearer. "Thought 1" 
could make a different but valid Alternative instance, after all. 
Prototype implementations are given... so it's clearly still O(1).

thought 1:
(=|=) :: P s a -> P s a -> P s a
a =|= b = ((peek a <> peek b) `onlyIf` (error "BUG in (=|=) user"))
               // (a // b)

thought 2:
(=|=) :: Eq a => P s a -> P s a -> P s a
a =|= b = ((peek a <> peek b) `onlyIf` (check))
               // (a // b)
   where
    check (ra,rb) = if ra /= rb then error "BUG in (=|=) user" else False
--This one "unnecessarily" requires Eq just to check a programmer's
--assertion of equivalence, but allows overlaps that give the same
--result.  On second thought... 'a' and 'b' could consume different
--amounts of input and produce the same result, so this is buggy.

thought 3:
symmetricDifference :: P s a -> P s a -> P s a
a `symmetricDifference` b =
        (doesNotMatch a ->> b) // (doesNotMatch b ->> a)

feeding arbitrary inputs using quickcheck should hopefully catch
incorrect usages of the (=|=)s that can be used in error, since it is
well known that one cannot systematically determine for all PEG parsers
whether the assertion will hold true (it must be at least as difficult
as determining whether any two are exactly equivalent).  HOWEVER it 
would also be interesting to see a similar system that could be 
restricted enough that one could show the correctness of such a 
non-intersection claim (I wonder how frequently such claims are fairly 
trivial to prove correct, anyway)


Isaac