易于指定为依赖类型但实施起来复杂的程序有哪些很好的例子？

Question

去年我问了“”。投票最多的答案提出了以下推理：

The hope is that your specification is simple and small enough to judge by examination, while your implementation of that might be far larger.

这种推理对我来说很有意义。 Idris 是测试这些概念最容易使用的语言；然而，由于它几乎可以像 Haskell 一样使用，因此它通常会让程序员在旧概念中徘徊，而不知道在哪里应用依赖类型。一些现实世界的例子可以帮助解决这个问题，因此，在实践中发生的好的、具体的程序示例，可以简单地表达为类型，但实施起来却很复杂？

Answer 1

我来回答：

often it leaves the programmer wandering through old concepts, without knowing where to apply dependent types

某些类型可用于消除某些类型的愚蠢错误，例如当您以错误的顺序将函数应用于其参数时，但这并不是类型的真正用途。类型构建您的推理并允许放大您的计算结构。

假设你处理列表并经常使用 head 和 tail，但这些是部分函数，所以你决定切换到更安全的东西，现在你处理 NonEmpty a 而不是[a]。然后你意识到你还做了很多 lookups（又是部分函数）并且在这种特殊情况下静态维护列表的长度不会太麻烦，所以你切换到 NonEmptyVec n a，其中 n 是向量的静态已知长度。现在您已经消除了许多可能的错误，但这不是发生的最重要的事情。

最重要的是，现在您可以查看类型签名，了解期望什么样的输入函数以及它们产生什么样的输出。函数的可能行为已通过其类型签名缩小，现在更容易识别函数在管道中的位置。而且你拥有的类型越详细，你的实体就越封装：类型 NonEmpty a -> b 的函数不再依赖于将传递给它的非空列表的假设，而是明确要求此不变量抓住。您已经将果冻状的紧耦合计算变成了细粒度计算。

丰富类型的作用是指导人类（在编写代码之前、编写代码期间、编写代码之后）并首先降低他们产生错误的能力——而不是为了事后发现错误。简单类型我认为是不可避免的，因为即使你用动态类型语言写代码，你还是要区分字符串和图片。

闲聊够了，这里是一个实用的真实世界示例，更重要的是，依赖类型的自然性。在 Servant 库的帮助下，我的目标是 API（这是一段很棒的代码，也是依赖类型的，所以你可能想检查一下）：

type API a r = ReqBody '[JSON] (Operation a) :> Post '[JSON] (Result r)

所以我们发送一个Operation a类型的请求（由Servant自动编码为JSON）并接收一个Result r响应（由Servant从JSON自动解码） . Operation 和 Result 定义如下：

data Method = Add | Get

data Operation a = Operation
  { method :: !Method
  , params :: !a
  }

data Result a = Result
  { result :: !a
  }

任务是执行操作并从服务器接收响应。然而问题在于，当我们 Add 时，服务器响应 AddResults，而当我们 Get 时，服务器的响应取决于我们与 [=30= 一起传递的内容] 方法。所以我们写一个类型族：

type family ResultOf m a where
  ResultOf Add a               = AddResults
  ResultOf Get DictionaryNames = Dictionaries

代码比我上面的描述更好读。只剩下将 Methods 提升到类型级别，所以我们定义一个合适的单例（这是目前在 Haskell 中模拟依赖类型的方式）：

data SMethod m where
  SAdd :: SMethod Add
  SGet :: SMethod Get

这里是主函数的类型签名（省略了很多不相关的东西）：

perform :: SMethod m -> a -> ClientM (ResultOf m a)

perform 接收单例形式的方法和一些值，returns Servant 的 ClientM monad 中的计算。此计算 returns 结果的类型取决于方法和值的类型：如果我们 SAdd，我们得到 AddResults；如果我们 SGet DictionaryNames，我们得到 Dictionaries。非常明智和自然 — 无需发明在哪里应用依赖类型：任务非常需要它们。

Answer 2

这对我来说很奇怪，因为我的问题是到处都需要依赖类型。如果你没有看到，那么就这样看程序。

假设我们有 f :: Ord a => [a] -> [a]（我将使用 Haskell 符号）。我们对这个函数了解多少 f？换句话说，对于 f []、f [5,8,7]、f [1,1,2,2] 等应用程序，您能预测到什么？假设你知道 f x = [4,6,8] 那么你对 x 有什么看法？如您所见，我们知之甚少。

那假设我告诉你f的真名是sort。关于这些相同的例子，你能告诉我什么？关于 ys 与 f xs = ys 中 xs 的关系，你能告诉我什么？现在你知道的很多了，但是这些信息是从哪里来的呢？我所做的只是更改函数的名称；这在程序的正式意义上没有意义。

所有这些新信息都来自您对排序的了解。你知道两个定义特征：

sort xs 是 xs.
sort xs 单调递增。

我们可以使用依赖类型来证明 sort 的这两个属性。那么，这不仅仅是我们对排序的外在理解的问题；排序的意义成为程序的固有部分。

捕捉错误是一种副作用。真正的 objective 是作为程序的一部分，将我们头脑中必须知道的内容具体化和形式化。

仔细重新考虑您已经编写的程序。有哪些只在您头脑中才知道的使您的程序运行的事实？这些都是候选示例。

易于指定为依赖类型但实施起来复杂的程序有哪些很好的例子？

What are good examples of programs that are simple to specify as dependent types, but complex to implement?

haskell

functional-programming

dependent-type

idris