Почему эта функция вешает REPL?

Question

В главе 9 " Разработка через тестирование с помощью Idris" представлен следующий тип данных и removeElem функция.

import Data.Vect

data MyElem : a -> Vect k a -> Type where
   MyHere  : MyElem x (x :: xs)
   MyThere : (later : MyElem x xs) -> MyElem x (y :: xs)

-- I slightly modified the definition of this function from the text.
removeElem : (value : a) -> (xs : Vect (S n) a) -> (prf : MyElem value xs) -> Vect n a
removeElem value (value :: ys) MyHere         = ys
removeElem value (y :: ys)    (MyThere later) = removeElem value (y :: ys) (MyThere later)

Следующие работы:

*lecture> removeElem 1 [1,2,3] MyHere
[2, 3] : Vect 2 Integer

Но следующий вызов все еще выполняется через несколько минут:

*lecture> removeElem 2 [1,2,3] (MyThere MyHere)

Полагаю, почему сборка такая медленная?

Answer 1

Второй случай вашего removeElem читает

removeElem value (y :: ys)    (MyThere later) = removeElem value (y :: ys) (MyThere later)

Правая сторона точно такая же, как левая; так что ваша рекурсия расходится. Вот почему оценка зависает.

Обратите внимание, что Идрис поймал бы эту ошибку, если бы вы заявили, что removeElem должно быть общее:

total removeElem : (value : a) -> (xs : Vect (S n) a) -> (prf : MyElem value xs) -> Vect n a
removeElem value (value :: ys) MyHere         = ys
removeElem value (y :: ys)    (MyThere later) = removeElem value (y :: ys) (MyThere later)

что приводит к ошибке во время компиляции

RemoveElem.idr строка 9 цв 0:

Main.removeElem возможно не является полным из-за рекурсивного пути Main.removeElem