Eu estava fazendo um exercício de código em Agda do PLFA, para implementar uma prova de que "o reverso de uma lista anexada a outra é o reverso da segunda anexada ao reverso da primeira".
reverse-++-distrib : ∀ {A : Set} → (xs ys : List A) → reverse (xs ++ ys) ≡ reverse ys ++ reverse xs
Consegui fazer os dois primeiros casos de indução sem problemas:
reverse-++-distrib {A} [] ys
reverse-++-distrib xs []
mas o terceiro passo tem um erro "Falha na verificação de terminação", o que eu acho que significa que o passo indutivo não foi feito corretamente.
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))
∎
A chamada problemática aparentemente é esta:
reverso-++-distribuição {A} (x :: []) xs
Para mim, isso parece bom porque o comprimento do primeiro argumento é 1, que é menor ou igual ao comprimento de x :: xs. E só é igual se xs for a lista vazia, caso em que deve entrar no segundo padrão de correspondência. Então, por que agda está tendo problemas com essa definição?
Agda está bem longe de ser capaz de adivinhar esse tipo de argumento do nada. O verificador de terminação apenas garante que os argumentos para a função fiquem estruturalmente menores a cada chamada (uma vez adequadamente ordenados lexicograficamente), mas sua função não atende a esse requisito porque
x ∷ []
não é estruturalmente menor quex ∷ xs
(pode ser igual, como você notou).Você pode pensar que isso é restritivo, mas muitas vezes revela uma maneira mais natural de estruturar programas e provas: por exemplo, aqui, você pode contornar isso transformando-o
reverse-++-distrib [ x ] xs
em um lema separadoreverse-∷-distrib x xs : reverse (x ∷ xs) ≡ reverse xs ++ [ x ]
.PS: seu último passo é apenas
refl
, já que[] ++ xs = xs
por definição.