Views in Idris - 清单 10.5 of Type-Driven Development in Idris book

Question

目前我正在阅读 Edwin Brady 的 "Type-Driven Development with Idris" 文本。不用说，文本列出了 SplitList 和 splitList（覆盖函数）的代码。但是，我想知道文本中给出的覆盖函数是否可以简化为我在下面生成的函数——它没有按预期工作。有人可以让我知道为什么我的 splitList 不起作用吗？我收到的错误消息在下面进一步产生。非常感谢。

data SplitList : List ty -> Type where
  Null      : SplitList [ ]
  Singleton : SplitList [x]
  Pair      : (lhs: List ty) -> (rhs: List ty) -> SplitList (lhs ++ rhs)

splitList : (xs: List ty) -> SplitList xs
splitList [ ] = Null
splitList [x] = Singleton
splitList xs  = 
  let 
    mid = div (List.length xs) 2 
    lhs = List.take mid xs
    rhs = List.drop mid xs
  in
    Pair lhs rhs

错误信息：

类型检查./foo.idr foo.idr:53:11: 使用预期类型检查 splitList 的右侧时拆分列表 xs

类型不匹配 SplitList (lhs ++ rhs) （配对类型 lhs rhs）和 SplitList xs（预期类型）

具体来说：类型不匹配左轴 ++ 右轴和 xs 洞数：Main.splitList

Answer 1

这个错误信息的原因是 Idris 没有看到 xs = lhs ++ rhs，你必须说服 Idris。

首先，让我们将上述事实作为一个单独的引理来证明：

total
takeDropAppend : (n : Nat) -> (xs : List ty) -> xs = List.take n xs ++ List.drop n xs
takeDropAppend Z _ = Refl
takeDropAppend (S n) [] = Refl
takeDropAppend (S n) (x :: xs) = cong $ takeDropAppend n xs

现在我们可以如下使用它：

total
splitList : (xs: List ty) -> SplitList xs
splitList [ ] = Null
splitList [x] = Singleton
splitList xs =
  let
    mid = divNatNZ (List.length xs) 2 SIsNotZ
  in
    rewrite takeDropAppend mid xs in
    Pair (List.take mid xs) (List.drop mid xs)

我将 div 更改为 divNatNZ 以使函数完整并采取了快捷方式，将 lhs 和 rhs 替换为它们的定义。我应该使用（更有效的）List.splitAt 标准函数，但它会使证明变得复杂。

Views in Idris - 清单 10.5 of Type-Driven Development in Idris book

Views in Idris - Listing 10.5 of Type-Driven Development in Idris book

types

idris

错误信息：