Nie mogę podać przyczyny, dlaczego tak się dzieje, ale mogę pokazać, jak leczyć objawy. Zanim zacznę: jest to known problem z funkcją sprawdzania zakończenia. Jeśli jesteś dobrze zorientowany w Haskell, możesz rzucić okiem na source.
Jednym z możliwych rozwiązań jest podział funkcji na dwa: pierwszy dla przypadku, gdy pierwszy argument staje się mniejsza, a drugi do drugiego:
mutual
merge : List ℕ → List ℕ → List ℕ
merge (x ∷ xs) (y ∷ ys) with x ≤? y
... | yes _ = x ∷ merge xs (y ∷ ys)
... | no _ = y ∷ merge′ x xs ys
merge xs ys = xs ++ ys
merge′ : ℕ → List ℕ → List ℕ → List ℕ
merge′ x xs (y ∷ ys) with x ≤? y
... | yes _ = x ∷ merge xs (y ∷ ys)
... | no _ = y ∷ merge′ x xs ys
merge′ x xs [] = x ∷ xs
Więc pierwsze kotlety funkcyjne dół xs i kiedy musimy odciąć ys, przełączamy się na drugą funkcję i na odwrót.
Innym (być może zaskakujące) opcja, która jest również wymieniona w raporcie emisyjnej, jest wprowadzenie wynik rekursji poprzez with:
merge : List ℕ → List ℕ → List ℕ
merge (x ∷ xs) (y ∷ ys) with x ≤? y | merge xs (y ∷ ys) | merge (x ∷ xs) ys
... | yes _ | r | _ = x ∷ r
... | no _ | _ | r = y ∷ r
merge xs ys = xs ++ ys
i wreszcie możemy wykonać Rekurencja na Vec torsach, a następnie konwersja z powrotem na List:
open import Data.Vec as V
using (Vec; []; _∷_)
merge : List ℕ → List ℕ → List ℕ
merge xs ys = V.toList (go (V.fromList xs) (V.fromList ys))
where
go : ∀ {n m} → Vec ℕ n → Vec ℕ m → Vec ℕ (n + m)
go {suc n} {suc m} (x ∷ xs) (y ∷ ys) with x ≤? y
... | yes _ = x ∷ go xs (y ∷ ys)
... | no _ rewrite lem n m = y ∷ go (x ∷ xs) ys
go xs ys = xs V.++ ys
Jednak tutaj musimy prosty lemat:
open import Relation.Binary.PropositionalEquality
lem : ∀ n m → n + suc m ≡ suc (n + m)
lem zero m = refl
lem (suc n) m rewrite lem n m = refl
Mogliśmy również mieć go zwrot List bezpośrednio i całkowicie uniknąć lematu:
merge : List ℕ → List ℕ → List ℕ
merge xs ys = go (V.fromList xs) (V.fromList ys)
where
go : ∀ {n m} → Vec ℕ n → Vec ℕ m → List ℕ
go (x ∷ xs) (y ∷ ys) with x ≤? y
... | yes _ = x ∷ go xs (y ∷ ys)
... | no _ = y ∷ go (x ∷ xs) ys
go xs ys = V.toList xs ++ V.toList ys
Pierwszy trik (tj podzielenie funkcji na kilka wzajemnie rekurencyjnych) jest całkiem niezłe do zapamiętania. Ponieważ kontroler rozwiązanie nie wygląda wewnątrz definicjami innych funkcji, których używasz, to odrzuca wiele perfekcyjnie programów, należy rozważyć:
data Rose {a} (A : Set a) : Set a where
[] : Rose A
node : A → List (Rose A) → Rose A
A teraz chcielibyśmy wdrożyć mapRose:
mapRose : ∀ {a b} {A : Set a} {B : Set b} →
(A → B) → Rose A → Rose B
mapRose f [] = []
mapRose f (node t ts) = node (f t) (map (mapRose f) ts)
Kontroler sprawdzania nie znajduje się wewnątrz map, aby sprawdzić, czy nie robi nic ciekawego z elementami i po prostu odrzuca tę definicję.Musimy inline definicję map i napisać parę funkcji wzajemnie rekurencyjnych:
mutual
mapRose : ∀ {a b} {A : Set a} {B : Set b} →
(A → B) → Rose A → Rose B
mapRose f [] = []
mapRose f (node t ts) = node (f t) (mapRose′ f ts)
mapRose′ : ∀ {a b} {A : Set a} {B : Set b} →
(A → B) → List (Rose A) → List (Rose B)
mapRose′ f [] = []
mapRose′ f (t ∷ ts) = mapRose f t ∷ mapRose′ f ts
Zazwyczaj można ukryć większość bałaganu w deklaracji where:
mapRose : ∀ {a b} {A : Set a} {B : Set b} →
(A → B) → Rose A → Rose B
mapRose {A = A} {B = B} f = go
where
go : Rose A → Rose B
go-list : List (Rose A) → List (Rose B)
go [] = []
go (node t ts) = node (f t) (go-list ts)
go-list [] = []
go-list (t ∷ ts) = go t ∷ go-list ts
UWAGA: Deklarowanie podpisy zarówno funkcje przed ich zdefiniowaniem mogą być używane zamiast mutual w nowszych wersjach Agdy.
Aktualizacja: Wersja rozwój Agda dostał aktualizację modułu sprawdzania zakończenia, dam commit wiadomość i zwolnić notatki mówią same za siebie:
- Rewizja zakończeniu połączenia milimetrowym które mogą zajmować się arbitralną głębokością zakończenia. Algorytm ten od jakiegoś czasu siedzi w MiniAgdzie, czekając na swój wspaniały dzień. Teraz jest tutaj! Opcja --terminacja-głębokość może teraz zostać wycofana.
I od informacji o wydaniu: sprawdzić
Zakończenie funkcji zdefiniowanych przez 'z' została poprawiona.
Przypadki, które wcześniej wymagały --termination-głębokość (teraz nieaktualne!) zdać sprawdzania zakończenia (ze względu na stosowanie „z”) nie dłuższy
trzeba flagę. Na przykład
merge : List A → List A → List A
merge [] ys = ys
merge xs [] = xs
merge (x ∷ xs) (y ∷ ys) with x ≤ y
merge (x ∷ xs) (y ∷ ys) | false = y ∷ merge (x ∷ xs) ys
merge (x ∷ xs) (y ∷ ys) | true = x ∷ merge xs (y ∷ ys)
ten nie kontroli zakończenia uprzednio, od „na” rozszerza się dodatkową funkcję scalania-AUX:
merge-aux x y xs ys false = y ∷ merge (x ∷ xs) ys
merge-aux x y xs ys true = x ∷ merge xs (y ∷ ys)
tej funkcji połączenia na połączenie, w którym wielkość jeden z argumentów rośnie. Aby to zrobić, sprawdzanie zakończenia teraz dodaje definicję merge-aux przed sprawdzeniem, a tym samym skutecznie kończy sprawdzanie oryginalnego programu źródłowego.
W wyniku tej transformacji wykonanie 'with' na zmiennej nie powoduje dłuższego zatrzymania. Na przykład, to nie robi czek zakończenia:
bad : Nat → Nat
bad n with n
... | zero = zero
... | suc m = bad m
i rzeczywiście, oryginalna funkcja przechodzi teraz czek zakończenia!
Dziękuję, to tylko odpowiedź, której szukałem. –