Skip to content

Instantly share code, notes, and snippets.

@damhiya
damhiya / Syntax.v
Last active June 14, 2025 13:52
Intrinsically well-scoped de Bruijn representation with fancy notation
From Coq Require Import String.
From stdpp Require Import base strings.
Section AUX.
#[global] Instance option_eq_dec_normalizable A `{dec : EqDecision A} : EqDecision (option A).
Proof.
intros x y. destruct x as [x|], y as [y|].
- destruct (decide (x = y)).
+ left. congruence.
{-# OPTIONS --safe #-}
module Cubical.HITs.CauchyReal.Base where
open import Cubical.Foundations.Prelude
open import Cubical.Data.Rationals.Base
open import Cubical.Data.Rationals.Order
open import Cubical.Data.Rationals.Properties
open import Cubical.Data.PositiveRational.Base
-- Higher inductive-inductive construction of Cauchy real, as in the HoTT book.
@damhiya
damhiya / Minimization.v
Last active June 8, 2025 07:52
Minimization
From Coq Require Import Lia.
Section TERMINATION.
Inductive terminate (P : nat -> Prop) : nat -> Prop :=
| found : forall n, P n -> terminate P n
| step : forall n, terminate P (S n) -> terminate P n
.
Fixpoint terminate_ind_dep
@damhiya
damhiya / Quotient.v
Last active May 12, 2025 07:12
quotient
Set Primitive Projections.
From Coq Require
Program
Logic.ProofIrrelevance
Logic.PropExtensionality
Logic.FunctionalExtensionality
Logic.Epsilon
Relations.Relation_Operators.
From Coq Require Fin.
Definition ifun (X Y : nat -> Type) : Type := forall i, X i -> Y i.
Definition δ (X : nat -> Type) (n : nat) := X (S n).
Definition prod (X Y : nat -> Type) (n : nat) := (X n * Y n)%type.
Definition sum (X Y : nat -> Type) (n : nat) := (X n + Y n)%type.
Definition TermF' (X : nat -> Type) := sum (δ X) (prod X X).
Variant TermF (X : nat -> Type) : nat -> Type :=
@damhiya
damhiya / bits.v
Created August 26, 2024 16:56
Breaking subject reduction in Coq using positive coinductive types
CoInductive bits : Set :=
| c0 : bits -> bits
| c1 : bits -> bits.
Lemma bits_eta : forall xs, match xs with
| c0 xs' => c0 xs'
| c1 xs' => c1 xs'
end = xs.
Proof.
intro xs. destruct xs; reflexivity.
@damhiya
damhiya / FAlg.hs
Last active May 23, 2024 03:58
recursor
data I = T | F
data TreeF :: (I -> Type) -> (I -> Type) where
Tip :: Int -> TreeF f T
Forest :: f F -> TreeF f T
Nil :: TreeF f F
Cons :: f T -> f F -> TreeF f F
data Tree :: I -> Type where
Fold :: TreeF Tree i -> Tree i
let and = fn (b1 : bool) -> fn (b2 : bool) ->
if b1 then b2 else false in
let or = fn (b1 : bool) -> fn (b2 : bool) ->
if b1 then true else b2 in
let map = fn (f : int * int * int -> int * int * int) ->
fix (mapf : list (int * int * int) -> list (int * int * int)) xs ->
case xs of
{ [] -> [] of (int * int * int)
; x :: xs -> f x :: mapf xs
} in
# Tetrahedron
# volume = 1/6
# area = (3 + sqrt 3)/2
tetrahedronMesh =
let vmap = [ 0. 1. 0. 0.
; 0. 0. 1. 0.
; 0. 0. 0. 1.
]
fmap = [ 0 0 0 1
@damhiya
damhiya / list-nixos-profile.sh
Last active July 15, 2023 13:55
nixos profile management
#!/usr/bin/env bash
PROFILE_PATH=/nix/var/nix/profiles
get_list() {
find $PROFILE_PATH -type l \
| awk "match(\$0, /^${PROFILE_PATH//\//\\\/}\/system-([0-9]*)-link\$/, res) { print res[1] }" \
| sort
}
get_current() {