Idris: Nachweis, dass bestimmte Begriffe sind unmöglich

Question

Idris Version: 0.9.16

---

I Konstruktionen aus einem base Wert und einer iterierten step Funktion erzeugt, zu beschreiben versucht bin:

namespace Iterate 
    data Iterate : (base : a) -> (step : a -> a) -> a -> Type where 
    IBase : Iterate base step base 
    IStep : Iterate base step v -> Iterate base step (step v) 

Mit diesem kann ich define Plus, beschreibt Konstrukte von iterierten Addition eines jump Wertes:

namespace Plus 
    Plus : (base : Nat) -> (jump : Nat) -> Nat -> Type 
    Plus base jump = Iterate base (\v => jump + v) 

Einfaches Beispiel nutzt dafür:

namespace PlusExamples 
    Even : Nat -> Type; Even = Plus 0 2 
    even0 : Even 0; even0 = IBase 
    even2 : Even 2; even2 = IStep even0 
    even4 : Even 4; even4 = IStep even2 

    Odd : Nat -> Type; Odd = Plus 1 2 
    odd1 : Odd 1; odd1 = IBase 
    odd3 : Odd 3; odd3 = IStep odd1 

    Fizz : Nat -> Type; Fizz = Plus 0 3 
    fizz0 : Fizz 0; fizz0 = IBase 
    fizz3 : Fizz 3; fizz3 = IStep fizz0 
    fizz6 : Fizz 6; fizz6 = IStep fizz3 

    Buzz : Nat -> Type; Buzz = Plus 0 5 
    buzz0 : Buzz 0; buzz0 = IBase 
    buzz5 : Buzz 5; buzz5 = IStep buzz0 
    buzz10 : Buzz 10; buzz10 = IStep buzz5 

Die folgende dass Werte unterhalb der base sind unmöglich beschreibt: zwischen base und jump + base für Werte

noLess : (base : Nat) -> 
      (i : Fin base) -> 
      Plus base jump (finToNat i) -> 
      Void 
    noLess Z  FZ  m  impossible 
    noLess (S b) FZ  IBase impossible 
    noLess (S b) (FS i) IBase impossible 

Und der folgende:

noBetween : (base : Nat) -> 
       (predJump : Nat) -> 
       (i : Fin predJump) -> 
       Plus base (S predJump) (base + S (finToNat i)) -> 
       Void 
    noBetween b Z  FZ  m  impossible 
    noBetween b (S s) FZ  IBase impossible 
    noBetween b (S s) (FS i) IBase impossible 

---

Ich habe Probleme definieren, die folgende Funktion:

noJump : (Plus base jump n -> Void) -> Plus base jump (jump + n) -> Void 
noJump f m = ?noJump_rhs 

Das heißt: wenn n nicht base plus ein natürliches Vielfaches von jump, dann ist weder jump + n.

Wenn ich Idris nach Fall split m frage zeigt es mir nur IBase - dann bleibe ich stecken.

Würde mir jemand in die richtige Richtung zeigen?

---

bearbeiten 0: Anwendung induction-m gibt mir die folgende Meldung:

Induction needs an eliminator for Iterate.Iterate.Iterate 

---

Edit 1: Name des Updates und hier ist eine Kopie der Quelle: http://lpaste.net/125873

Answer 1

Zum bearbeiten 0: auf einer Art induct, braucht es eine besondere Qualifier:

%elim data Iterate = <your definition> 

auf die Hauptfrage: sorry, dass ich nicht durch den gesamten Code gelesen habe, möchte ich nur einen Vorschlag machen um Beweise zu verfälschen. Aus meiner Erfahrung (ich vertiefte sogar die Standardbibliothek Quellen, um etwas Hilfe zu finden), wenn Sie Not a (a -> Void) beweisen müssen, können Sie oft Not b (b -> Void) und eine Möglichkeit a in b zu konvertieren, dann übergeben Sie es einfach zum zweiten Beweis.Zum Beispiel kann eine sehr einfache Beweis dafür, dass eine Liste nicht-Präfix eines anderen sein, wenn sie unterschiedliche Köpfe haben:

%elim data Prefix : List a -> List a -> Type where 
    pEmpty : Prefix Nil ys 
    pNext : Prefix xs ys -> Prefix (x :: xs) (x :: ys) 

prefixNotCons : Not (x = y) -> Not (Prefix (x :: xs) (y :: ys)) 
prefixNotCons r (pNext _) = r refl 

In Ihrem Fall, nehme ich Sie mehrere Beweise kombinieren müssen.