是否有可能定义一个简单的相等语法概念(类似于GHC可能自动派生为Haskell 98类型的Eq实例),而不显式地证明每个数据构造函数是内射的,或者执行类似的操作,例如定义每个构造函数的回缩和使用cong?
换句话说,是否有可能更直接地利用数据构造函数的内射性,而不是每个构造函数引入一个辅助函数?
下面以自然数为例。
module Eq where
open import Function
open import Relation.Binary
open import Relation.Binary.PropositionalEquality
open import R
我有一个编程语言的AST的数据类型,我想解释一下,但AST大约有10个不同的构造函数。
data Term : Set where
UnitTerm : Term
VarTerm : Var -> Term
...
SeqTerm : Term -> Term -> Term
我正在尝试编写一个函数,它对这种语言的语法树具有可判定的等价性。从理论上讲,这很简单:没有什么太复杂的,它只是存储在AST中的简单数据。
问题是,编写这样一个函数似乎需要大约100个用例:对于每个构造函数,有10个用例。
eqDecide : (x : Term) -> (y
Inductive ty: Set :=
| I
| O.
Definition f (x: ty) (y: ty): nat :=
if x = y then 0 else 1.
我希望函数f比较ty类型的两个术语,但是它没有编译,我看到了这个错误:
术语x = y有Prop类型,它不是(共同)归纳类型.
我正在试着解决这个问题。希望有人能帮上忙。
假设我们有一个名为Confusion的程序;
Program confusion
if(Virus-Finder(Confusion) = false) then
infect-executable
else
halt
End program confusion
显然这是伪代码,所以不会运行。
对于任何程序P,我们可以运行Virus-Finder(P),如果是病毒,则结果为True,如果不是,则结果为False。
infect-executable是一个模块,它扫描内存中的可执行程序,并在这些可执行程序中复制程序Confusion。
我们
我对哈斯克尔很陌生,只是玩了一会儿。
我编写了一个轻量级的OOP仿真:
--OOP.hs
{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, UndecidableInstances, ScopedTypeVariables, FunctionalDependencies #-}
module OOP where
class Provides obj iface where
provide::obj->iface
(#>)::obj->(iface->a)->a
o #>
我一直在尝试使用免费的monads;作为学习辅助,我已经设法为以下Free类型编写了一个Show实例:
{-# LANGUAGE FlexibleContexts, UndecidableInstances #-}
-- Free monad datatype
data Free f a = Return a | Roll (f (Free f a))
instance Functor f => Monad (Free f) where
return = Return
Return a >>= f = f a
Roll ffa >>=
对于自然数nat这样的简单归纳型,很容易证明两个构造函数(0和后继)给出了所有可能的自然数,
Lemma nat_destruct (n : nat) : n = O \/ exists m : nat, n = S m.
Proof.
destruct n. left. reflexivity. right. exists n. reflexivity.
Qed.
然而,我听说平等证明并不是那么简单。只有一个等式构造函数eq_refl,但是Coq不能证明
eq_destruct : forall (A : Type) (x : A) (prEq : x = x), prEq = eq_r
你能解释一下吗,我怎么能检查一下,第一个上下文无关语法(G1)的语言是第二个上下文无关语法(G2)语言的子集。
G1和G2是两个字母相同的LL(1)语法:
{a, b, c, d, f}
生产规则如下:
A -> αB
或
A -> α
α是一个非epsilon字符串(由终端符号组成).
上下文无关语法G1:
S1 -> aK
K -> bC|cE
C -> cB|d
E -> bA|f
A -> abC
B -> acE
上下文无关语法G2:
S2 -> aX
X -> bZ|cY
Z -> cV|d
Y -> bU
为什么这种类型的单一用法会编译,但将其放入列表会失败呢?
ft1 :: (Foldable t, Num a) => t a -> a
ft1 = (F.foldl (+) 0)
fTest :: [(Foldable t, Num a) => t a -> a ]
fTest = [ F.foldl (+) 0 ]
后者给出了错误:
folding.hs:80:10:
Illegal polymorphic or qualified type:
(Foldable t, Num a) => t a -> a
Pe