Coq. Ile dalga geçiyorum. Özellikle, mergesort uygulamak ve daha sonra çalıştığını kanıtlamak için çalışıyorum. bir uygulama olarak Coq'da Fixpoint Sınırlamaları?
girişimim
oldu:Error:
Recursive definition of sort is ill-formed.
In environment
sort : list nat -> list nat
ls : list nat
x : nat
l : list nat
y : nat
l0 : list nat
left : list nat
right : list nat
Recursive call to sort has principal argument equal to "left" instead of
one of the following variables: "l" "l0".
Recursive definition is:
"fun ls : list nat =>
match ls with
| nil => nil
| x :: nil => x :: nil
| x :: _ :: _ =>
let (left, right) := split ls nil nil in merge (sort left) (sort right)
end".
Bu hataların Benim yorumum bu l ve l0 olmadan ls şunlardır:
Fixpoint sort ls :=
match ls with
| nil => nil
| cons x nil => cons x nil
| xs =>
let (left, right) := split xs nil nil
in merge (sort left) (sort right)
end.
Bunun bir sonucu olarak elde hataları vardır x'in başı, x ve x'den sonraki ögesi (ben de aramaya karar verdim sanırım). Bu listelerden birinde yinelemediğim ve yerel olarak tanımlanmış bir listeye tekrar girdiğim için kızgınım.
Sadece desen eşlemesinden gelen şeylerin tekrarlanmasına izin verildim mi? Evet ise, bu ciddi bir sınırlama gibi görünüyor. Etrafında yollar var mı? Coq'un işlevin sonlanacağını söyleyemediğini tahmin ediyorum. Sola ve sağa xs'den daha küçük olduğunu kanıtlamanın bir yolu var mı?
http://adam.chlipala.net/cpdt/html/GeneralRec.html
Haklı nedenlere dayanan tekrarlama adlı bölümü okuyunuz, bir anlamda kadar sağlam temellere dayanan özyineleme kullanarak birleştirme uygular: