Agda: Формирование всех пар {(x, y) | x в xs, y в ys}

Question

Мне интересно, какой лучший способ приблизиться к пониманию списков или декартовых продуктов в Агда.

У меня есть два вектора, xs и ys. Я хочу (неформальный) набор {(x, y) | x в xs, y в ys}.

Я могу довольно легко сформировать этот набор, используя карту и CONCAT:

allPairs : {A : Set} -> {m n : ℕ} -> Vec A m -> Vec A n -> Vec (A × A) (m * n) 
allPairs xs ys = Data.Vec.concat (Data.Vec.map (λ x -> Data.Vec.map (λ y -> (x , y)) ys ) xs) 

Отсюда, я хотел бы кое-что для получения свидетельства для пар, что-то вроде:

pairWitness : ∀ {A} -> {m n : ℕ} -> (xv : Vec A m) -> (yv : Vec A n) -> (x : A) -> (y : A) -> x ∈ xv -> y ∈ yv -> (x , y) ∈ allPairs xv yv 

Я надеваю Не знаю, как построить такого свидетеля. Насколько я могу судить, я теряю слишком много первоначальной структуры векторов, чтобы иметь возможность использовать мои индуктивные случаи.

Я задаюсь

1. Есть ли что-то в стандартной библиотеке дело с такого рода «все пары» операции, которые уже доказали Леммы, как это?
2. Если нет, то как мне поступить о создании свидетеля пары?

Answer 1

Я загрузил a self-contained version of the code со всеми необходимыми импортными товарами, чтобы вам было легче играть с кодом.

Важно, чтобы увидеть структуру конечного вектора, который вы получаете при запуске allPairs: вы получаете m куски размером n с точным рисунком.

• Первый фрагмент является листинг пары, состо щей из головки xv вместе с каждым из элементов в yv.

• (...)

• п-я порция листинг пары, состоящие из п-го элемента xv вместе с каждым из элементов в yv.

Все эти блоки соединены при помощи конкатенации (_++_). Чтобы иметь возможность выбрать один кусок (потому что в нем находится нужный x) или пропустить его (потому что x дальше), вы должны ввести промежуточные теоремы, описывающие взаимодействие между _++_ и _∈_.

Вы должны быть в состоянии знать, как выбрать кусок (в случае, если x в этом), что соответствует этой простой промежуточной лемме:

_∈xs++_ : {A : Set} {x : A} {m : ℕ} {xs : Vec A m} 
      (prx : x ∈ xs) {n : ℕ} (ys : Vec A n) → x ∈ xs ++ ys 
here  ∈xs++ ys = here 
there pr ∈xs++ ys = there (pr ∈xs++ ys) 

Но вы также должны быть в состоянии пропустить кусок (в случае x находится дальше), которая соответствует этой другой леммы:

_∈_++ys : {A : Set} {x : A} {n : ℕ} {ys : Vec A n} 
      (prx : x ∈ ys) {m : ℕ} (xs : Vec A m) → x ∈ xs ++ ys 
pr ∈ []  ++ys = pr 
pr ∈ x ∷ xs ++ys = there (pr ∈ xs ++ys) 

Наконец, после того как вы выбрали правильный кусок, вы можете заметить, что она была создана с использованием map так: Vec.map (λ y -> (x , y)) ys. Ну, одна вещь, которую вы можете доказать, что map совместим с членскими доказательствами:

_∈map_xs : {A B : Set} {x : A} {m : ℕ} {xs : Vec A m} 
      (prx : x ∈ xs) (f : A → B) → f x ∈ Vec.map f xs 
here  ∈map f xs = here 
there pr ∈map f xs = there (pr ∈map f xs) 

Теперь вы можете положить все это вместе и производят свидетельство индукцией по доказательству x ∈ xs:

pairWitness : {A : Set} {m n : ℕ} (xv : Vec A m) (yv : Vec A n) 
       {x y : A} -> x ∈ xv -> y ∈ yv -> (x , y) ∈ allPairs xv yv 
pairWitness (x ∷ xv) yv here pry = pry ∈map (λ y → x , y) xs ∈xs++ allPairs xv yv 
pairWitness (x ∷ xv) yv (there prx) pry = pairWitness _ _ prx pry ∈ Vec.map (λ y → x , y) yv ++ys