为什么这个函数会挂起REPL？

Question

Test-Driven Development with Idris 的第 9 章介绍了以下数据类型和 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 应该是总计，Idris 会发现此错误：

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 line 9 col 0:

Main.removeElem is possibly not total due to recursive path Main.removeElem

为什么这个函数会挂起REPL？

Why does this function hang the REPL?

recursion

idris

partial-functions

totality