Liste Gleichheit w/`cong`

Question

Im Anschluss an meine anderen question, ich versuchte, die tatsächliche Übung in Type-Driven Development with Idris für same_cons zu beweisen, dass bei zwei gleiche Listen vor dem gleichen Element zu jeder Liste in zwei gleiche Listen führt.

Beispiel:

prove that 1 :: [1,2,3] == 1 :: [1,2,3]

So kam ich mit dem folgenden Code auf, die kompiliert:

sameS : {xs : List a} -> {ys : List a} -> (x: a) -> xs = ys -> x :: xs = x :: ys 
sameS {xs} {ys} x prf = cong prf 

same_cons : {xs : List a} -> {ys : List a} -> xs = ys -> x :: xs = x :: ys 
same_cons prf = sameS _ prf 

ich anrufen kann es über:

> same_cons {x=5} {xs = [1,2,3]} {ys = [1,2,3]} Refl 
Refl : [5, 1, 2, 3] = [5, 1, 2, 3] 

In Bezug auf die cong Funktion , mein Verständnis ist, dass es einen Beweis braucht, dh a = b, aber ich verstehe sein zweites Argument nicht: f a.

> :t cong 
cong : (a = b) -> f a = f b 

Bitte erläutern.

Answer 1

Wenn Sie zwei Werte haben u : c und v : c, und eine Funktion f : c -> d, dann, wenn Sie wissen, dass u = v es, dass f u = f v zu folgen hat, nach nur aus Referenz Transparenz.

cong ist der Beweis für die obige Aussage.

In diesem speziellen Anwendungsfall, setzen Sie (via Vereinigung) c und d-List a, u-xs, v zu ys und f zu (:) x, da Sie, dass xs = ys -> (:) x xs = (:) x ys beweisen wollen.