How do I prove a “seemingly obvious” fact when relevant types are abstracted by a lambda in Idris?

Question

I am writing a basic monadic parser in Idris, to get used to the syntax and differences from Haskell. I have the basics of that working just fine, but I am stuck on trying to create VerifiedSemigroup and VerifiedMonoid instances for the parser.

Without further ado, here's the parser type, Semigroup, and Monoid instances, and the start of a VerifiedSemigroup instance.

data ParserM a          = Parser (String -> List (a, String))
parse                   : ParserM a -> String -> List (a, String)
parse (Parser p)        = p
instance Semigroup (ParserM a) where
    p <+> q             = Parser (\s => parse p s ++ parse q s)
instance Monoid (ParserM a) where
    neutral             = Parser (const []) 
instance VerifiedSemigroup (ParserM a) where
    semigroupOpIsAssociative (Parser p) (Parser q) (Parser r) = ?whatGoesHere

I'm basically stuck after intros, with the following prover state:

-Parser.whatGoesHere> intros
----------              Other goals:              ----------
{hole3},{hole2},{hole1},{hole0}
----------              Assumptions:              ----------
 a : Type
 p : String -> List (a, String)
 q : String -> List (a, String)
 r : String -> List (a, String)
----------                 Goal:                  ----------
{hole4} : Parser (\s => p s ++ q s ++ r s) =
          Parser (\s => (p s ++ q s) ++ r s)
-Parser.whatGoesHere> 

It looks like I should be able to use rewrite together with appendAssociative somehow, but I don't know how to "get inside" the lambda \s.

Anyway, I'm stuck on the theorem-proving part of the exercise - and I can't seem to find much Idris-centric theorem proving documentation. I guess maybe I need to start looking at Agda tutorials (though Idris is the dependently-typed language I'm convinced I want to learn!).

Answer 1

The simple answer is that you can't. Reasoning about functions is fairly awkward in intensional type theories. For example, Martin-Löf's type theory is unable to prove:

S x + y = S (x + y)
0   + y = y

x +′ S y = S (x + y)
x +′ 0   = x

_+_ ≡ _+′_  -- ???

(as far as I know, this is an actual theorem and not just "proof by lack of imagination"; however, I couldn't find the source where I read it). This also means that there is no proof for the more general:

ext : ∀ {A : Set} {B : A → Set}
        {f g : (x : A) → B x} →
        (∀ x → f x ≡ g x) → f ≡ g

This is called function extensionality: if you can prove that the results are equal for all arguments (that is, the functions are equal extensionally), then the functions are equal as well.

This would work perfectly for the problem you have:

<+>-assoc : {A : Set} (p q r : ParserM A) →
  (p <+> q) <+> r ≡ p <+> (q <+> r)
<+>-assoc (Parser p) (Parser q) (Parser r) =
  cong Parser (ext λ s → ++-assoc (p s) (q s) (r s))

where ++-assoc is your proof of associative property of _++_. I'm not sure how would it look in tactics, but it's going to be fairly similar: apply congruence for Parser and the goal should be:

(\s => p s ++ q s ++ r s) = (\s => (p s ++ q s) ++ r s)

You can then apply extensionality to get assumption s : String and a goal:

p s ++ q s ++ r s = (p s ++ q s) ++ r s

---

However, as I said before, we don't have function extensionality (note that this is not true for type theories in general: extensional type theories, homotopy type theory and others are able to prove this statement). The easy option is to assume it as an axiom. As with any other axiom, you risk:

• Losing consistency (i.e. being able to prove falsehood; though I think function extensionality is OK)

• Breaking reduction (what does a function that does case analysis only for refl do when given this axiom?)

I'm not sure how Idris handles axioms, so I won't go into details. Just beware that axioms can mess up some stuff if you are not careful.

---

The hard option is to work with setoids. A setoid is basically a type equipped with custom equality. The idea is that instead of having a Monoid (or VerifiedSemigroup in your case) that works on the built-in equality (= in Idris, ≡ in Agda), you have a special monoid (or semigroup) with different underlying equality. This is usually done by packing the monoid (semigroup) operations together with the equality and bunch of proofs, namely (in pseudocode):

=   : A → A → Set  -- equality
_*_ : A → A → A    -- associative binary operation
1   : A            -- neutral element

=-refl  : x = x
=-trans : x = y → y = z → x = z
=-sym   : x = y → y = x

*-cong : x = y → u = v → x * u = y * v  -- the operation respects
                                        -- our equality

*-assoc : x * (y * z) = (x * y) * z
1-left  : 1 * x = x
1-right : x * 1 = x

The choice of equality for parsers is clear: two parsers are equal if their outputs agree for all possible inputs.

-- Parser equality
_≡p_ : {A : Set} (p q : ParserM A) → Set
Parser p ≡p Parser q = ∀ x → p x ≡ q x

This solution comes with different tradeoffs, namely that the new equality cannot fully substitute the built-in one (this tends to show up when you need to rewrite some terms). But it's great if you just want to show that your code does what it's supposed to do (up to some custom equality).