Sınırları besleyen sınırlar ve tabiatlar arasında izomorfizm kurmak?

Question

İdriste, Fin n ve (x ** So (x < n)) arasında bir izomorfizm kurabilir misiniz? (Ben aslında Idris'u bilmiyorum, bu yüzden bu tipler geçerli olmayabilir. Genel fikir, n'dan daha az bir yapım yapılacağı ve test yoluyla n'dan daha az olduğu garanti edilen bir veri tipine sahip olduğumuzdur. .)

Answer 1

Burada, İdris'teki bir kanıt var 0.10.2 Görebildiğiniz gibi, roundtrip2 tek zor kanıttır. Ne var olmayan bir önermeler So (x < n) yerine x `LT` n ise

import Data.Fin 
%default total 

Bound : Nat -> Type 
Bound n = DPair Nat (\x => x `LT` n) 

bZ : Bound (S n) 
bZ = (0 ** LTESucc LTEZero) 

bS : Bound n -> Bound (S n) 
bS (x ** bound) = (S x ** LTESucc bound) 

fromFin : Fin n -> Bound n 
fromFin FZ = bZ 
fromFin (FS k) = bS (fromFin k) 

toFin : Bound n -> Fin n 
toFin (Z ** LTEZero) impossible 
toFin {n = S n} (Z ** bound) = FZ 
toFin (S x ** LTESucc bound) = FS (toFin (x ** bound)) 

roundtrip1 : {n : Nat} -> (k : Bound n) -> fromFin (toFin k) = k 
roundtrip1 (Z ** LTEZero) impossible 
roundtrip1 {n = S n} (Z ** LTESucc LTEZero) = Refl 
roundtrip1 (S x ** LTESucc bound) = rewrite (roundtrip1 (x ** bound)) in Refl 

roundtrip2 : {n : Nat} -> (k : Fin n) -> toFin (fromFin k) = k 
roundtrip2 FZ = Refl 
roundtrip2 (FS k) = rewrite (lemma (fromFin k)) in cong {f = FS} (roundtrip2 k) 
    where 
    lemma : {n : Nat} -> (k : Bound n) -> toFin (bS k) = FS (toFin k) 
    lemma (x ** pf) = Refl 

, sen geçirmez forma dönüştürmek gerekir. Bu seferki Böyle yapmak başardı:

Aslında

import Data.So 

%default total 

stepBack : So (S x < S y) -> So (x < y) 
stepBack {x = x} {y = y} so with (compare x y) 
    | LT = so 
    | EQ = so 
    | GT = so 

correct : So (x < y) -> x `LT` y 
correct {x = Z} {y = Z}  Oh impossible 
correct {x = S _} {y = Z}  Oh impossible 
correct {x = Z} {y = S _} so = LTESucc LTEZero 
correct {x = S x} {y = S y} so = LTESucc $ correct $ stepBack so