- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
在 Idris/Haskell 中,可以通过注释类型并使用 GADT 构造函数来证明数据的属性,例如使用 Vect,但是,这需要将属性硬编码到类型中(例如,Vect 必须是与列表)。是否可以使用具有开放属性集的类型(例如同时包含长度和运行平均值的列表),例如通过重载构造函数或使用 Effect 的方式?
最佳答案
我相信 McBride 在他的 ornament paper (pdf) 中回答了这个问题(对于类型理论) 。您正在寻找的概念是代数装饰的概念(强调我的):
An algebra φ describes a structural method to interpret data, giving rise to a fold φ oper- ation, applying the method recursively. Unsurprisingly, the resulting tree of calls to φ has the same structure as the original data — that is the point, after all. But what if that were, before all, the point? Suppose we wanted to fix the result of fold φ in advance, representing only those data which would deliver the answer we wanted. We should need the data to fit with a tree of φ calls which delivers that answer. Can we restrict our data to exactly that? Of course we can, if we index by the answer.
现在,让我们编写一些代码。我已经把整个事情了in a gist因为我要在这里插入评论。另外,我正在使用 Agda,但它应该很容易转换为 Idris。
module reornament where
我们首先定义传递 B
作用于 A
列表的代数意味着什么。我们需要一个基本情况(B
类型的值)以及将列表头部与归纳假设结合起来的方法。
ListAlg : (A B : Set) → Set
ListAlg A B = B × (A → B → B)
根据这个定义,我们可以定义一种由 B
索引的 A
列表,其值正是与给定 对应的计算结果>ListAlg A B
。在 nil
情况下,结果是代数 (proj₁ alg
) 提供给我们的基本情况,而在 cons
情况下,我们只需使用第二个投影将归纳假设与新头部结合起来:
data ListSpec (A : Set) {B : Set} (alg : ListAlg A B) : (b : B) → Set where
nil : ListSpec A alg (proj₁ alg)
cons : (a : A) {b : B} (as : ListSpec A alg b) → ListSpec A alg (proj₂ alg a b)
好的,现在让我们导入一些库并看几个示例:
open import Data.Product
open import Data.Nat
open import Data.List
计算列表长度的代数由作为基本情况的 0
和作为组合 A
的方式的 const suc
给出和尾部的长度来构建当前列表的长度。因此:
AlgLength : {A : Set} → ListAlg A ℕ
AlgLength = 0 , (λ _ → suc)
如果元素是自然数,那么它们可以相加。与之对应的代数以 0
作为基本情况,以 _+_
作为将 ℕ
与元素之和组合在一起的方式包含在尾部。因此:
AlgSum : ListAlg ℕ ℕ
AlgSum = 0 , _+_
疯狂的想法:如果我们有两个代数处理相同的元素,我们可以将它们组合起来!这样我们将跟踪 2 个不变量而不是一个!
Alg× : {A B C : Set} (algB : ListAlg A B) (algC : ListAlg A C) →
ListAlg A (B × C)
Alg× (b , sucB) (c , sucC) = (b , c) , (λ a → λ { (b , c) → sucB a b , sucC a c })
现在是例子:
如果我们跟踪长度,那么我们可以定义向量:
Vec : (A : Set) (n : ℕ) → Set
Vec A n = ListSpec A AlgLength n
例如,长度为 4 的向量:
allFin4 : Vec ℕ 4
allFin4 = cons 0 (cons 1 (cons 2 (cons 3 nil)))
如果我们跟踪元素的总和,那么我们可以定义分布的概念:统计分布是总和为 100 的概率列表:
Distribution : Set
Distribution = ListSpec ℕ AlgSum 100
例如,我们可以定义一个统一的:
uniform : Distribution
uniform = cons 25 (cons 25 (cons 25 (cons 25 nil)))
最后,通过结合长度代数和和代数,我们可以实现大小分布的概念。
SizedDistribution : ℕ → Set
SizedDistribution n = ListSpec ℕ (Alg× AlgLength AlgSum) (n , 100)
并为 4 个元素集提供良好的均匀分布:
uniform4 : SizedDistribution 4
uniform4 = cons 25 (cons 25 (cons 25 (cons 25 nil)))
关于haskell - Haskell/Idris 中的开放类型级别证明,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27219660/
(这不是关于定理证明,而是关于实践中的测试,例如 quickCheck) 让f一些通用函数 f :: RESTRICTIONS => GENERICS 具有一些“理想的”属性(即不是 hack,是不可
给定数组 arr 和索引数组 ind,以下算法就地重新排列 arr 以满足给定的索引: function swap(arr, i, k) { var temp = arr[i]; arr[i]
我有兴趣创建一个具有运行时间和空间限制的简单数组问题。看来我找到了解决问题的方法。请阅读以下java代码中问题的初始描述注释: /* * Problem: Given two integer ar
我是 isabelle 的新手,并试图证明以下简单的不等式: lemma ineq: "(a::real) > 0 ⟹ a 0 ⟹ b 0" proof have "1/a + 1/b >
是否有任何理论说缓存应该比文件系统更快? 我认为,由于文件系统也使用缓存,因此没有科学证据表明当文件系统的概念有些松散时,我们应该将内容从文件系统移动到诸如 memcache 之类的缓存中——比如下载
我正在做一个证明,我的一个子目标看起来有点像这样: Goal forall (a b : bool) (p: Prop) (H1: p -> a = b) (H2: p), neg
我有定义的归纳类型: Inductive InL (A:Type) (y:A) : list A -> Prop := | InHead : forall xs:list A, InL y (co
我知道 CRC 是一个线性函数,这意味着 CRC(x xor y) = CRC(x) xor CRC(y),但我不知道如何证明 CRC 的这个属性。 有谁有想法吗? 非常感谢! 最佳答案 这通常不是真
我是 Coq 的初学者。 虽然计算机为我验证了证明令人满意,但众所周知,满足 Coq 的证明对人类来说难以阅读。这是一个简单的例子,假设您没有看到任何评论: Theorem add_comm : fo
我试图了解是什么决定了类型参数是否必须是标称的。 虽然 GADT 和类型家族在某种意义上看起来不同,但它们不是“简单容器”,因为它们的实例定义可以“查看”它们的参数,但简单类型是否可以明显需要名义参数
我想使用 function 关键字定义来证明函数定义的正确性。以下是自然数的通常归纳定义上的加法函数的定义: theory FunctionDefinition imports Main begin
我定义了一个 Sygma-Type,如下所示: { R : nat -> nat -> bool | Reflexive R } 我有两个元素 r1 r2 : { R : nat -> nat ->
我有以下数据: new_pairs x y Freq start.latittude start.longitude start.station end.la
出于教育目的,我一直试图通过使用各种语言扩展和单例类型,在 Haskell 中重建《Type-Driven Development with Idris》(即 RemoveElem.idr )一书中的
我定义了一个 Sygma-Type,如下所示: { R : nat -> nat -> bool | Reflexive R } 我有两个元素 r1 r2 : { R : nat -> nat ->
我正在使用Ax DevTools,并且试图弄清楚如何使用相同的构建信息标记多个扫描。现在,我的测试运行如下: class MyTestCase : XCTestCase { func myTest
我正在尝试证明一个函数的正确性,该函数检查数组是否按递增/递减顺序排序或未排序。行为是返回 -1,如果按降序排序,1,如果按升序排序,大小为 1,或包含相同的值,0,如果没有已排序或为空。运行:Fra
我试图证明 Z3(Microsoft 的 SMT 求解器)中的一个归纳事实。我知道 Z3 通常不提供此功能,如 Z3 guide 中所述。 (第 8 节:数据类型),但是当我们限制要证明事实的域时,这
问题已编辑: 如代码中所述,HashSet 和 HashMap 是快速失败的(但这不是保证): void goHashSet() { Set set = new HashSet();
我试图使导航栏中的链接延伸到导航栏的全长。我环顾四周,发现了一些有用的信息,但无法使其正常工作 HTML: To
我是一名优秀的程序员,十分优秀!