这个递归函数不是完全的，还是编译器无法证明它？如何将其重写为总计？

Question

出现以下代码时：

module TotalityOrWhat

%default total

data Instruction = Jump Nat | Return Char | Error

parse : List Char -> Instruction
parse ('j' :: '1' :: _) = Jump 1
parse ('j' :: '2' :: _) = Jump 2
parse ('j' :: '3' :: _) = Jump 3
parse ('r' :: x :: _) = Return x
parse _ = Error

parseDriver : String -> Maybe Char
parseDriver = parseDriver' . unpack where
  parseDriver' : List Char -> Maybe Char
  parseDriver' xs =
    case parse xs of
      (Jump j) => parseDriver' $ drop j xs
      (Return x) => Just x
      Error => Nothing

Idris报错：

TotalityOrWhat.idr:17:3:
TotalityOrWhat.parseDriver, parseDriver' is possibly not total due to recursive path
TotalityOrWhat.parseDriver, parseDriver' --> TotalityOrWhat.parseDriver, parseDriver'

TotalityOrWhat.idr:15:1:
TotalityOrWhat.parseDriver is possibly not total due to:
TotalityOrWhat.parseDriver, parseDriver'

我已经用其他几种方式重写了这段代码，但无法让 Idris 将其识别为完整代码。我认为它是完全的是错误的，还是伊德里斯只是无法确定它是？如果它本质上是完全的，我如何重写它以便 Idris 将它识别为完全？

Answer 1

这不是 "why isn't it recognized as total" 的答案，甚至不是 "how do I change it to be recognized as total" 的真正答案，但既然你提到了

I have re-written this code in several other ways but cannot get Idris to recognize it as total,

我认为您可能对解决方法感兴趣。如果你手动内联parse到parseDriver'，你可以通过totality checker得到它：

total parseDriver : String -> Maybe Char
parseDriver = parseDriver' . unpack where
  parseDriver' : List Char -> Maybe Char
  parseDriver' ('j' :: '1' :: xs) = parseDriver' ('1' :: xs)
  parseDriver' ('j' :: '2' :: xs) = parseDriver' xs
  parseDriver' ('j' :: '3' :: _ :: xs) = parseDriver' xs
  parseDriver' ('r' :: x :: _) = Just x
  parseDriver' _ = Nothing

这是可行的，因为我们总是在结构上递归 xs 的某些后缀。

Answer 2

这里的问题是 Idris 无法知道 drop j xs 从其输入中生成一个严格较小的列表，因为 drop 的类型表达能力不够。

因此，另一种 ad-hoc 方法是使用一个虚拟参数，通过在调用时使用结构较小的列表 xs' 使完整性检查器接受该函数parseDriver'递归。

parseDriver : String -> Maybe Char
parseDriver s = parseDriver' chars chars where
  chars : List Char
  chars = unpack s

  -- 2nd parameter is a dummy one (to make totality checker happy)
  parseDriver' : List Char -> List Char -> Maybe Char
  parseDriver' _  [] = Nothing
  parseDriver' xs (_::xs') =
    case parse xs of
      Jump j => parseDriver' (drop j xs) xs'
      Return x => Just x
      Error => Nothing

我们也可以使用一些自然参数 n，我们可以在每一步递减它，确保我们在 0 处停止。 n的初始值自然可以是输入列表的长度。

这个递归函数不是完全的，还是编译器无法证明它？如何将其重写为总计？

Is this recursive function not total, or is the compiler just unable to prove it? How to rewrite it as total?

recursion

pattern-matching

idris

totality