小编Rod*_*iro的帖子

在我正在处理的形式化中，我需要将 Unit 类型从在 UniverseSet上定义的 Agda 标准库提升为像Set a.

我怎样才能做到这一点？我知道我可以定义另一种类型，就像这样：

record Unit {l} : Set l where
   constructor unit

这是宇宙多态。但是，我认为应该有一个更惯用的解决方案来解决这个问题。有人可以为我提供解决方案，或者如果无法向我解释原因吗？

我正在使用Idris中经过认证的正则表达式匹配器的形式化(我相信在任何基于类型理论的证明助手中都存在相同的问题,例如Agda和Coq)并且我坚持如何定义补语的语义操作.我有以下数据类型来表示正则表达式的语义:

data InRegExp : List Char -> RegExp -> Type where
 InEps : InRegExp [] Eps
 InChr : InRegExp [ a ] (Chr a)
 InCat : InRegExp xs l ->
         InRegExp ys r ->
         zs = xs ++ ys ->
         InRegExp zs (Cat l r)
 InAltL : InRegExp xs l ->
          InRegExp xs (Alt l r)
 InAltR : InRegExp xs r ->
          InRegExp xs (Alt l r)
 InStar : InRegExp xs (Alt Eps (Cat e (Star e))) ->
          InRegExp xs …

考虑以下简单的表达式语言:

Inductive Exp : Set :=
| EConst : nat -> Exp
| EVar   : nat -> Exp
| EFun   : nat -> list Exp -> Exp.

及其良好的谓词:

Definition Env := list nat.

Inductive WF (env : Env) : Exp -> Prop :=
| WFConst : forall n, WF env (EConst n)
| WFVar   : forall n, In n env -> WF env (EVar n)
| WFFun   : forall n es, In n env ->
                         Forall (WF env) es -> …

在Haskell中,可以在大小索引列表上编写函数,以确保我们永远不会超出范围.可能的实现是:

data Nat = Zero | Succ Nat deriving (Eq, Ord, Show)

infixr 5 :-

data Vec (n :: Nat) a where
    Nil  :: Vec 'Zero a
    (:-) :: a -> Vec n a -> Vec ('Succ n) a       

data Fin (n :: Nat) where
    FZ :: Fin ('Succ n)
    FS :: Fin n -> Fin ('Succ n)                       

vLookup :: Vec n a -> Fin n -> a
vLookup Nil _ = undefined           
vLookup (x :- _) FZ = x …

我正在尝试使用一些Haskell扩展来实现一个简单的DSL.我想要的一个功能是为变量提供类型级别上下文.我知道这种事情在像Agda或Idris这样的语言中很常见.但我想知道是否有可能在Haskell中实现相同的结果.

我的想法是使用类型级别关联列表.代码如下:

{-# LANGUAGE GADTs, 
         DataKinds, 
         PolyKinds, 
         TypeOperators, 
         TypeFamilies, 
         ScopedTypeVariables, 
         ConstraintKinds, 
         UndecidableInstances #-}

import Data.Proxy    
import Data.Singletons.Prelude   
import Data.Singletons.Prelude.List

import GHC.Exts    
import GHC.TypeLits

type family In (s :: Symbol)(a :: *)(env :: [(Symbol, *)]) :: Constraint where
     In x t '[] = ()
     In x t ('(y,t) ': env) = (x ~ y , In x t env)


data Exp (env :: [(Symbol, *)]) (a :: *) where
     Pure :: a -> Exp env a
     Map  :: (a -> b) …

正如我之前所说,我正在一个关于代数,矩阵和范畴理论的图书馆工作.我已经在记录类型的"塔"中分解了代数结构,每个代表一个代数结构.例如,为了指定一个monoid,我们首先定义一个半群并定义一个可交换的monoid,我们使用monoid定义,遵循与Agda标准库相同的模式.

我的麻烦的是,当我需要的代数结构,它是内另一个深(例如的属性的属性Monoid是的一部分CommutativeSemiring),我们需要使用数量等于期望的代数结构深度的突起.

作为我的问题的一个例子,请考虑以下"引理":

open import Algebra
open import Algebra.Structures
open import Data.Vec
open import Relation.Binary.PropositionalEquality
open import Algebra.FunctionProperties
open import Data.Product

module _ {Carrier : Set} {_+_ _*_ : Op? Carrier} {0# 1# : Carrier} (ICSR : IsCommutativeSemiring _?_ _+_ _*_ 0# 1#) where

csr : CommutativeSemiring _ _
csr = record{ isCommutativeSemiring = ICSR }

zipWith-replicate-0# : ? {n}(xs : Vec Carrier n) ? zipWith _+_ (replicate 0#) xs ? xs
zipWith-replicate-0# [] …