如何在 Idris 中定义仅包含某些值组合的对类型

Question

我试图通过尝试一些超出我理解范围的方式来了解 Idris 中的依赖类型。如果我犯了任何愚蠢的错误，请多多包涵。

给定简单类型

data Letter = A | B | C | D

我想定义一个包含一对 Letter 的类型 LPair，这样只有 "neighboring" 个字母可以配对。例如，B 可以与 A 或 C 配对，但不能与 D 或其自身配对。它环绕，所以 A 和 D 被视为邻居。

实际上，给定 x : Letter 和 y : Letter，mklpair x y 将等同于 mklpair y x，但我不确定属性是否可以还是应该体现在类型上。

制作这种类型的最佳方法是什么？

Answer 1

最直接的方法是创建 (Letter, Letter) 的子集，其中元素满足谓词 (a, b : Letter) -> Either (Next a b) (Next b a)，其中 Next 只是右边的邻居：

data Letter = A | B | C | D

data Next : Letter -> Letter -> Type where
  AB : Next A B
  BC : Next B C
  CD : Next C D
  DA : Next D A

Neighbour : Letter -> Letter -> Type
Neighbour a b = Either (Next a b) (Next b a)

LPair : Type
LPair = (p : (Letter, Letter) ** Neighbour (fst p) (snd p))

mklpair : (a : Letter) -> (b : Letter) -> {auto prf : Neighbour a b} -> LPair
mklpair a b {prf} = ((a, b) ** prf)

N.B.: 这种方法既好又简单，但是一旦你实现了一个函数来决定 a 和 b 是否彼此相邻，你将需要(number of letters)^3 个案例：

isNext : (a : Letter) -> (b : Letter) -> Dec (Next a b)
isNext A A = No nAA where
  nAA : Next A A -> Void
  nAA AB impossible
  nAA BC impossible
  nAA CD impossible
  nAA DA impossible
isNext A B = Yes AB
...

如果你有很多字母并且需要一个决策函数，那么通常的方法是将你的数据映射到一个递归类型，比如 Nat。由于您的模数大小写 (Next D A)，您需要像这样的包装器：

data NextN : Nat -> Nat -> Nat -> Type where
  NextS : {auto prf :      (S a) `LTE` m}  -> NextN m a (S a) -- succ in mod m
  NextZ : {auto prf : Not ((S a) `LTE` m)} -> NextN m a Z     -- wrap around

LToN : Letter -> Nat
LToN A = 0
LToN B = 1
LToN C = 2
LToN D = 3

LNeighbour : Letter -> Letter -> Type
LNeighbour x y =
  let a = LToN x
      b = LToN y
  in Either (NextN 3 a b) (NextN 3 b a)

LNPair : Type
LNPair = (p : (Letter, Letter) ** LNeighbour (fst p) (snd p))

mklnpair : (a : Letter) -> (b : Letter) -> {auto prf : LNeighbour a b} -> LNPair
mklnpair a b {prf} = ((a, b) ** prf)

使用 NextS 和 NextZ 你只有两种情况需要检查，而不是每个字母检查一种。

Answer 2

你需要的是字母相邻的证明。所以根据你对邻居的定义：

data Letter = A | B | C | D

neighbours : Letter -> Letter -> Bool
neighbours A B = True
neighbours B A = True
neighbours B C = True
neighbours C B = True
neighbours C D = True
neighbours D A = True
neighbours A D = True
neighbours _ _ = False

data LPair : Type where
  MkLPair : (x : Letter) -> (y : Letter) -> {auto prf : neighbours x y = True} -> LPair

{} 使 prf 参数隐式化，而 auto 告诉 Idris 自己弄明白。

如何在 Idris 中定义仅包含某些值组合的对类型

How to define a pair type in Idris that only holds certain combinations of values

dependent-type

idris