FAQ Database Discussion Community

## Agda: Simulate Coq's rewrite tactic

pattern-matching,proof,agda,dependent-type
I have some experience using Coq and am now in the process of learning Agda. I'm working on a correctness proof of insertion sort and have reached a point where I would like to perform something similar to Coq's rewrite tactic. Currently, I have: open import Data.Nat open import Relation.Binary.PropositionalEquality...

## How should the general type of a “lemma” function be understood?

Perhaps this is a stupid question. Here's a quote from the Hasochism paper: One approach to resolving this issue is to encode lemmas, given by parameterised equations, as Haskell functions. In general, such lemmas may be encoded as functions of type: ∀ x1 ... xn. Natty x1 → ... →...

## Can I have an unknown KnownNat?

I wonder if I can have my cake and eat it too regarding KnownNats. Can I write code that uses Nats that may be both KnownNats and UnknownNats (SomeNats?). For example if I have a dependently typed vector Vec (n :: Nat) a, can I write code that works both...

## What is the right way to typecheck dependent lambda abstraction using 'bound'?

I am implementing a simple dependently-typed language, similar to the one described by Lennart Augustsson, while also using bound to manage bindings. When typechecking a dependent lambda term, such as λt:* . λx:t . x, I need to: "Enter" the outer lambda binder, by instantiating t to something Typecheck λx:t...

## How can I express the type of 'takeWhile for vectors'?

Haskell beginner here. I've defined the following types: data Nat = Z | S Nat data Vector a n where Nil :: Vector a Z (:-) :: a -> Vector a n -> Vector a (S n) infixl 5 :- I'm trying to write the function, takeWhileVector which behaves the...

## Two-way conversion between integers and Peano naturals

scala,types,dependent-type,path-dependent-type
I am using a standard type-encoding of natural numbers in Scala. For the purpose of this question, the following definition will do: sealed trait Nat sealed trait _0 extends Nat sealed trait Succ[N <: Nat] extends Nat I can use the compiler to convert these Nat types into actual numbers,...

## Statically balanced trees in Agda

tree,agda,dependent-type
I'm teaching myself about dependent types by learning Agda. Here's a type for binary trees balanced by their size. open import Data.Nat open import Data.Nat.Properties.Simple data T (A : Set) : ℕ -> Set where empty : T A 0 leaf : A -> T A 1 bal : ∀...

## Coq: substitution and dependent types

equality,coq,dependent-type
I'm at an odd place trying to prove an equation: 1 subgoals A : Type s : set A x : A s0 : s x x0 : A s1 : s x0 H : x0 = x ______________________________________(1/1) stv s x0 s1 = stv s x s0 What I...

## In Idris, how to write a “vect generator” function that take a function of index in parameter

dependent-type,idris
I'm trying to write in Idris a function that create a Vect by passing the size of the Vect and a function taking the index in parameter. So far, I've this : import Data.Fin import Data.Vect generate: (n:Nat) -> (Nat -> a) ->Vect n a generate n f = generate'...

## Agda: pattern matching equal variables?

types,functional-programming,agda,dependent-type
As a learning experience, I'm trying to implement a verified regular-expression matcher using continuation-passing style in Agda, based on the one proposed in this paper. I've got a type for regular expressions defined like this: data RE : Set where ε : RE ∅ : RE Lit : Char ->...

## How to specify a number range as a type in Idris?

dependent-type,idris
I've been experimenting with Idris and it seems like it should be simple to specify some sort of type for representing all numbers between two different numbers, e.g. NumRange 5 10 is the type of all numbers between 5 and 10. I'd like to include doubles/floats, but a type for...

## Case class constructor argument type depending on the previous argument value

scala,case-class,dependent-type,dotty
I am trying to do the following trait Stateful { type State } case class SystemState(system: Stateful, state: system.State) // does not compile That is, the type of statedepends on (the value of) system. That, however, is not supported: illegal dependent method type: parameter appears in the type of another...

## Handling let in hypothesis

coq,proof,dependent-type
As an exercise in Coq, I'm trying to prove that the following function returns a pair of lists of equal length. Require Import List. Fixpoint split (A B:Set)(x:list (A*B)) : (list A)*(list B) := match x with |nil => (nil, nil) |cons (a,b) x1 => let (ta, tb) := split...