Вопрос или проблема
Проверка завершения Agda не удалась для упражнения reverse-++-distrib.
Я выполнял задачу по коду в Agda из PLFA, чтобы реализовать доказательство того, что “обратный порядок одного списка, добавленного к другому, равен обратному порядку второго списка, добавленного к обратному порядку первого”.
reverse-++-distrib : ∀ {A : Set} → (xs ys : List A) → reverse (xs ++ ys) ≡ reverse ys ++ reverse xs
Я смог сделать первые два случая индукции без проблем:
reverse-++-distrib {A} [] ys
reverse-++-distrib xs []
но третья стадия выдает ошибку “Проверка завершения не удалась”, что, я полагаю, означает, что индуктивный шаг выполнен неправильно.
reverse-++-distrib {A} (x :: xs) ys =
begin
reverse ((x :: xs) ++ ys)
≡⟨⟩
reverse (x :: (xs ++ ys))
≡⟨⟩
reverse (xs ++ ys) ++ [ x ]
≡⟨ cong (_++ [ x ]) (reverse-++-distrib xs ys) ⟩
(reverse ys ++ reverse xs) ++ [ x ]
≡⟨ ++-assoc (reverse ys) (reverse xs) [ x ] ⟩
reverse ys ++ (reverse xs ++ [ x ])
≡⟨ cong ((reverse ys) ++_) (cong ((reverse xs) ++_) (sym (reverse-++-fixed-point {A} x))) ⟩
(reverse ys) ++ (reverse xs ++ (reverse [ x ]))
**≡⟨ cong ((reverse ys) ++_) (sym (reverse-++-distrib {A} (x :: []) xs)) ⟩**
(reverse ys) ++ (reverse ([ x ] ++ xs))
≡⟨⟩
(reverse ys) ++ (reverse (x :: ([] ++ xs)))
≡⟨ cong ((reverse ys) ++_) (cong reverse (cong (x ::_) (++-identityˡ xs))) ⟩
(reverse ys) ++ (reverse (x :: xs))
∎
Проблемный вызов, по-видимому, это:
reverse-++-distrib {A} (x :: []) xs
Для меня это выглядит нормально, потому что длина первого аргумента равна 1, что меньше или равно длине x :: xs. И она равна, только если xs – пустой список, в этом случае он должен перейти ко второму сопоставлению с образцом. Так почему же у Agda возникают проблемы с этой определением?
Для меня это выглядит нормально, потому что длина первого аргумента равна 1, что меньше или равно длине x :: xs. И она равна, только если xs – пустой список, в этом случае он должен перейти ко второму сопоставлению с образцом. Так почему же у Agda возникают проблемы с этой определением?
Agda совсем не способна угадать такой аргумент на пустом месте. Проверка завершения только гарантирует, что аргументы функции становятся структурно меньше с каждым вызовом (при условии подходящего лексикографического порядка), но ваша функция не удовлетворяет этому требованию, потому что x ∷ [] не меньше структурно, чем x ∷ xs (как вы заметили, они могут быть равны).
Вы можете считать это ограничительным, но это часто показывает более естественный способ структурировать программы и доказательства: например, здесь вы можете обойти это, превратив reverse-++-distrib [ x ] xs в отдельную лемму reverse-∷-distrib x xs : reverse (x ∷ xs) ≡ reverse xs ++ [ x ].
П.С.: ваш последний шаг — это просто refl, так как [] ++ xs = xs по определению.
Ответ или решение
Проблема, с которой вы столкнулись в Agda, связана с тем, что проверка окончания (termination checking) не проходит из-за того, что аргумент функции не уменьшается структурно при рекурсивном вызове. Это происходит в вашем случае, когда вы пытаетесь вызвать reverse-++-distrib {A} (x :: []) xs, поскольку x :: [] не является строго меньшим, чем x :: xs.
Agda требует, чтобы для обеспечения корректности завершения рекурсивных вызовов аргументы функции должны быть «структурно меньшими» в каждом шаге рекурсии. В вашем случае ситуация такова, что длина x :: [] может быть равна длине x :: xs, если xs – пустой список, что не соответствует требованиям завершения.
Чтобы обойти эту проблему, вам следует рассмотреть возможность выделения отдельной леммы, которая будет решать эту частную задачу. Например, вы можете создать лему:
reverse-∷-distrib : ∀ {A : Set} → (x : A) → (xs : List A) → reverse (x :: xs) ≡ reverse xs ++ [ x ]Затем вы можете использовать эту лемму в вашем доказательстве. Вот как можно перестроить ваш код с добавлением этой леммы:
reverse-∷-distrib : ∀ {A : Set} → (x : A) → (xs : List A) → reverse (x :: xs) ≡ reverse xs ++ [ x ]
reverse-∷-distrib x xs = -- Ваша реализация леммы
reverse-++-distrib : ∀ {A : Set} → (xs ys : List A) → reverse (xs ++ ys) ≡ reverse ys ++ reverse xs
reverse-++-distrib {A} [] ys = refl
reverse-++-distrib {A} xs [] = -- Ваша реализация для второго случая
reverse-++-distrib {A} (x :: xs) ys =
begin
reverse ((x :: xs) ++ ys)
≡⟨⟩
reverse (x :: (xs ++ ys))
≡⟨⟩
reverse (xs ++ ys) ++ [ x ]
≡⟨ cong (_++ [ x ]) (reverse-++-distrib xs ys) ⟩
(reverse ys ++ reverse xs) ++ [ x ]
≡⟨ ++-assoc (reverse ys) (reverse xs) [ x ] ⟩
reverse ys ++ (reverse xs ++ [ x ])
≡⟨ cong ((reverse ys) ++_) (cong ((reverse xs) ++_) (sym (reverse-++-fixed-point {A} x))) ⟩
(reverse ys) ++ (reverse xs ++ (reverse [ x ]))
≡⟨ cong ((reverse ys) ++_) (sym (reverse-++-distrib {A} (x :: []) xs)) ⟩
(reverse ys) ++ (reverse ([ x ] ++ xs))
≡⟨⟩
(reverse ys) ++ (reverse (x :: ([] ++ xs)))
≡⟨ cong ((reverse ys) ++_) (cong reverse (cong (x ::_) (++-identityˡ xs))) ⟩
(reverse ys) ++ (reverse (x :: xs))
∎Теперь использование reverse-∷-distrib вместо вызова reverse-++-distrib {A} (x :: []) xs решит проблему с проверкой завершения, так как вы избежите ситуации, когда длины списков становятся равными.
Важно отметить, что последний шаг вашего доказательства идентичен refl, поскольку по определению [] ++ xs = xs.
Таким образом, лучшее решение заключается в правильной структуризации рекурсии и выделении отдельных лемм для частных случаев, что не только помогает пройти проверку на завершение, но и упрощает понимание доказательства.