I guess the easiest way is to use some standard Fin↔Nat conversion functions from Data.Fin: incr, decr : {n : Nat} -> Fin n -> Maybe (Fin n) incr {n=n} f = natToFin (succ $ finToNat f) n decr {n=n} f = case finToNat f of Z => Nothing S...

Unfortunately, the theorem that you want to prove here is not in fact true, because Idris naturals truncate subtraction at 0. A counterexample to your theorem1 is n=3, m=0. Let's step through the evaluation: First, we substitute: 3 + (0 - 3) = 0 Next, we desugar the syntax to...

The basic idea behind Agda's ↔ is to package up two functions with two proofs of roundtripping, which is easy enough to do in Idris as well: infix 7 ~~ data (~~) : Type -> Type -> Type where MkIso : {A : Type} -> {B : Type} -> (to...

You can use DecEq to make this easy: add : (x, y : Nat) -> x + y < 10 = True -> Nat add x y _ = x + y main : IO () main = let x = S Z in let y = Z in case...

Side channel attacks are for instance timing attacks, e.g. you can get information about the secrets by measuring timing differences when using different inputs. It is already hard to do this right in a low level language like C where you have lots of control about processor instructions, cache handling,...

syntactic-sugar,applicative,idris

I was able to get this working by taking care of two problems: if _ then _ else _ doesn't seem to propagate the idiom bracket to its subexpressions The default definition of if _ then _ else _ is (of course) lazy in its two branches, and Lazy' LazyEval...

The problem: powApplyI was not provably total, according to Idris. Idris' totality checker relies on being able to reduce parameters to structurally smaller forms, and with raw ZZs, this doesn't work. The answer is to delegate the recursion to plain old powApply (which is proven total): total powApplyI : ZZ...

It's really odd that people think pattern matching on types is bad. We get a lot of mileage out of pattern matching on data which encode types, whenever we do a universe construction. If you take the approach that Thorsten Altenkirch and I pioneered (and which my comrades and I...

Matching on a Type is known as type-casing. Being able to do this would break a concept called parametricity which is very valuable. http://stackoverflow.com/a/23224110/108359 Idris does not support type-casing. I think it may have tried at one stage, but people gave up on that quickly. It also used to give...

The problem with using -> in this way is that it's not a type constructor but a binder, where the name bound for the domain is in scope in the range, so -> itself doesn't have a type directly. Your definition of t for example wouldn't capture a dependent type...

This seems like a bug in the Idris typechecker that doesn't resolve overloaded functions even when they are completely determined by the type. To witness, I can make a proof like this: myLeftIdentity : (x : a) -> (f : a -> ErrorM b) -> return x >>= f =...

The type checker won't reduce natToChar because it isn't total - this is basically to prevent you using some partially defined function to prove something which isn't true. If you're writing this to work on data which turns up at run-time, possibly what you need is Dec or Maybe: natToChar...

There are two problems here. Firstly, in the 'case' block, the argument is strM rather than strM x as it is in the 'with' block, so you're inspecting different things. There's a more interesting problem though, which is that if you try fixing the first one: strSplit : String ->...

The key idea is that the first element of the vector is f 0, and for the tail, if you have k : Fin n, then FS k : Fin (S n) is a "shift" of the finite number that increments its value and its type at the same time....

logic,prefix,dependent-type,idris

I think the only problem here is that you've used [a] as the type of lists of a, in the Haskell style, whereas in Idris it needs to be List a. Your Prefix type looks fine to me, although I'd write it as: data Prefix : List a -> List...

Remember that unification is a syntactic operation, which in languages like Idris is augmented with straightforward reductions according to pattern-matching. It doesn't know all of the facts that we can prove! We can certainly prove in Idris that if n+m=0 then m = 0 and n = 0: sumZero :...

vector,linked-list,algebraic-data-types,idris

It doesn't do anything to optimise Vector lookups (at the time of writing this answer, at least). This isn't because of any difficulty in doing it, really, but more because I would rather have some kind of general framework for writing this kind of optimisation than hard coding lots of...

You were on the right track with your listSplit lemma. You can use that function to learn whether the target element is on the left or right side of a Tree. This is the relevant line from my implementation inTreeThenInorder x (branch y l r) e with listSplit x (inOrder...

I imagine the problem is the line subst' a1 a2 with (subst a2 a2) Don't you mean to call subst on a1 and a2, or the other way around?...

algebraic-data-types,idris,formal-verification

The induction tactic can only be used on types that were declared with %elim. Some people feel that Idris should be automatically generating eliminators whenever possible, but there would appear to be some technical difficulties with that. Could anybody give an example for, say, the aforementioned All? As far as...

verification,idris,coinduction

I was able to get a little help on IRC from Daniel Peebles (copumpkin) who explained that being able to use propositional equality over codata is just generally not something usually permitted. He pointed out that it's possible to define a custom equivalence relation, like how Agda defines ones for...

I think we were going to develop the wiki into more of a reference for this sort of thing: https://github.com/idris-lang/Idris-dev/wiki/Manual The syntax for postulate is: postulate identifier : type as in postulate n : Nat or postulate whyNot : 5 = 6 It introduces an unspecified value of that type....

It turns out all I need to do is enumerate all possible patterns for foo's argument, and then Idris is able to figure out, one by one, that they are un-unifyable with foo's type: foo : FunPtr [] b -> Void foo here impossible foo (there _) impossible ...

I have no clue if you will ever find a use for this, but I think the obvious translation should be class ListLike k where llElem : Type fromList : List llElem -> k instance ListLike (List a) where llElem = a fromList = id instance ListLike (Maybe a) where...

proof,agda,idris,proof-of-correctness,isar

Coq has extensive libraries covering real analysis. Various developments come to mind: the standard library and projects building on it such as the now defunct coqtail project [1] (with extensive coverage of power series and quite a bit of work on Complex numbers) or the more recent coquelicot. All of...

parsing,unification,idris,decidable

The error message is correct: you provided a value of type Type, but you need a value of type p '0'. You are also correct that p is of type Char -> Type, and therefore that p '0' is of type Type. However, p '0' is not of type p...

David Christiansen is working on something to automate this in general, and he is essentially finished; it can be found in his GitHub repository. In the mean time, here's an approach that can take you from O(n^2) cases to O(n) cases in this situation. First, some preliminaries. If you have...

The short answer is "No, not really", unfortunately. However, I don't like seeing bad error messages so if you can provide more details maybe it's something we can look into and improve. The longer answer is that there is a problem with the way Idris reports errors here, and I...

I've sort of solved this. For idris-interpreter-flags you must give each actual argument as a separate string (which is common, I should have known). So, if I set idris-interpreter-flags to '("-i" "/path/to/idris/libs/prelude") then all is good. So I have to add the path for each of the libraries' directories that...

haskell,proof,category-theory,correctness,idris

I believe that McBride has answered that question (for Type Theory) in his ornament paper (pdf). The concept you are looking for is the one of an algebraic ornament (emphasis mine): An algebra φ describes a structural method to interpret data, giving rise to a fold φ oper- ation, applying...

In practice, you may do better to simply check the bounds as needed, but you can certainly write a data type to enforce such a property. One straightforward way to do it is like this: data Range : Ord a => a -> a -> Type where MkRange : Ord...

vector,coq,idris,convoy-pattern

It's not possible to implement this function so easily in plain Coq: you need to rewrite your function using the convoy pattern. There was a similar question posted a while ago about this. The idea is that you need to make your match return a function in order to propagate...

haskell,lazy-evaluation,evaluation,expression-evaluation,idris

We say Idris has strict evaluation, but this is for its run-time semantics. Being a fully dependently typed language, Idris has two phases where it evaluates things, compile-time and run-time. At compile-time it will only evaluate things which it knows to be total (i.e. terminating and covering all possible inputs)...