标签: quantifiers

请问,这些表达方式之间有什么区别

x = x.replaceAll("\\s", "");
x = x.replaceAll("\\s+", "");

该哈斯克尔维基做了解释如何使用存在类型的一个很好的工作,但我不太神交背后的理论.

考虑这个存在类型的例子:

data S = forall a. Show a => S a      -- (1)

为我们可以转换为的东西定义一个类型包装器String.维基提到我们真正想要定义的是类似的类型

data S = S (exists a. Show a => a)    -- (2)

即一个真正的"存在主义"类型 - 松散地我认为这是"数据构造函数S采用Show实例存在并包装它的任何类型".事实上,你可能会写一个GADT如下:

data S where                          -- (3)
    S :: Show a => a -> S

我没有尝试过编译,但似乎它应该可行.对我来说,GADT显然等同于我们想写的代码(2).

然而,对我来说,完全不明白为什么(1)等同于(2).为什么将数据构造函数移到外面forall变成了exists？

我能想到的最接近的是De Morgan的逻辑定律,其中交换否定的顺序和量词将存在量词转换为通用量词,反之亦然:

¬(?x. px) ? ?x. ¬(px)

但是数据构造函数似乎与否定运算符完全不同.

使用forall而不是不存在来定义存在类型的能力背后的理论是什么exists？

我正在努力理解与existsHaskell类型系统相关的关键字.据我所知,默认情况下Haskell中没有这样的关键字,但是:

• 在这些声明中有扩展添加它们data Accum a = exists s. MkAccum s (a -> s -> s) (s -> a)
• 我已经看过一篇关于它们的论文,并且(如果我没记错的话)它声明exists关键字对于类型系统是不必要的,因为它可以通过forall

但我甚至不明白是什么exists意思.

当我说,forall a . a -> Int这意味着(在我的理解中,不正确的一个,我猜)"对于每个(类型)a,都有一个类型的函数a -> Int":

myF1 :: forall a . a -> Int
myF1 _ = 123
-- okay, that function (`a -> Int`) does exist for any `a`
-- because we have just defined it

当我说exists a . a -> …

如果要使用GHC的词法范围变量,则还必须使用显式通用量化.也就是说,您必须向forall函数的类型签名添加声明:

{-# LANGUAGE ExplicitForAll, ScopedTypeVariables #-}

f :: forall a . [a] -> [a]      -- The `forall` is required here ...
f (x:xs) = xs ++ [x :: a]       -- ... to relate this `a` to the ones above.

这实际上与量化有什么关系,或者扩展编写者是否只是将forall关键字作为一个方便的标记来应用新的,更广泛的范围？

换句话说,为什么我们不能forall像往常一样抛弃？是不是很清楚函数体内注释中的类型变量是否引用了函数签名中同名的变量？或者打字会不会有问题或含糊不清？

是否可以使用原子分组(或以其他方式)模拟占有量词(.NET不支持它)？

注意.我发现(x+x+)++y可以替换(?>(x+x+)+)y,但这只是一个例子,我不知道是否总是{something}@+等于(?>{something}@)(@量子的位置).

我正在阅读关于量词的Java教程.

贪婪,不情愿和占有量词之间的差异有所不同.

我无法理解究竟是什么区别.

解释如下:

Enter your regex: .*foo  // greedy quantifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfooxxxxxxfoo" starting at index 0 and ending at index 13.

Enter your regex: .*?foo  // reluctant quantifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfoo" starting at index 0 and ending at index 4.
I found the text "xxxxxxfoo" starting at index 4 and ending at index 13.

Enter your regex: .*+foo …

我一直在努力研究如何在Scala中实现Church编码的数据类型.它似乎需要rank-n类型,因为你需要一个类型的第一类const函数forAll a. a -> (forAll b. b -> b).

但是,我能够如此编码对:

import scalaz._

trait Compose[F[_],G[_]] { type Apply = F[G[A]] }

trait Closure[F[_],G[_]] { def apply[B](f: F[B]): G[B] }

def pair[A,B](a: A, b: B) =
  new Closure[Compose[({type f[x] = A => x})#f,
                      ({type f[x] = B => x})#f]#Apply, Id] {
    def apply[C](f: A => B => C) = f(a)(b)
  }

对于列表,我能够编码cons:

def cons[A](x: A) = {
  type T[B] = B => (A => B => …

这个问题出现在#haskell的讨论中.

如果它的出现是积极的,将深嵌套的forall提升到顶部是否总是正确的？

例如:

((forall a. P(a)) -> S) -> T

(其中P,S,T应理解为metavariables)

forall a. (P(a) -> S) -> T

(我们通常会写作 (P(a) -> S) -> T

我知道你肯定被允许从一些积极的位置收集foralls,例如在最后的右边->等等.

这在经典逻辑中是有效的,因此这不是一个荒谬的想法,但总的来说它在直觉逻辑中是无效的.然而,我的非正式博弈论量词的直觉,即每个类型变量"由来电者选择"或"由被叫者选择"表明实际上只有两个选择,你可以将所有"被来电者选择"选项提升到顶端.除非游戏中的移动交错很重要？

首先,让我解释一下,这个问题既不是关于如何捕获组,也不是关于如何使用量词,这是我非常熟悉的正则表达式的两个特征.对于可能熟悉异国情调引擎中不寻常语法的正则表达式爱好者而言,这是一个更高级的问题.

捕捉量词

有谁知道正则表达式的味道是否允许你捕捉量词？通过这个,我的意思是计数与+和*等量词匹配的字符数将被计算,并且这个数字可以在另一个量词中再次使用.

例如,假设您要确保在此类字符串中具有相同数量的Ls和Rs:LLLRRRRR

你可以想象一下这样的语法

L(+)R{\q1}

其中捕获了L的+量词,并且在R的量词中将捕获的数字称为{\ q1}

这对平衡{@,=, - ,/}在字符串中的数量很有用,例如@@@@"星球大战"===="1977"----"科幻小说"////"乔治卢卡斯"

与递归的关系

在某些情况下,量词捕获会优雅地替换递归,例如由相同数量的Ls和Rs构成的一段文本,a in

L(+) some_content R{\q1} 

这个想法在下面的页面中有一些细节:Captifured Quantifiers

它还讨论了捕获量化的自然扩展:量化算术,适用于您希望匹配(3*x + 1)之前匹配的字符数的情况.

我试图找出这样的事情是否存在.

在此先感谢您的见解!

更新

Casimir给出了一个很棒的答案,它显示了两种方法来验证模式的各个部分具有相同的长度.但是,我不想在日常工作中依赖其中任何一种.这些都是表现出色表演的伎俩.在我看来,这些美丽但复杂的方法证实了这个问题的前提:一个正则表达式特征来捕获量化的字符数(例如+或*)能够匹配将使这种平衡模式非常简单并扩展语法一种令人愉快的表达方式.

更新2(稍后)

我发现.NET有一个接近我所询问的功能.添加了演示该功能的答案.

在Eloquent JavaScript 第9章:正则表达式下的" 解析INI文件 "一节中,有一个例子,其中包含一个我根本没有捕获的正则表达式.作者试图解析下一个内容:

searchengine=http://www.google.com/search?q=$1
spitefulness=9.7

; comments are preceded by a semicolon...
; each section concerns an individual enemy
[larry]
fullname=Larry Doe
type=kindergarten bully
website=http://www.geocities.com/CapeCanaveral/11451

[gargamel]
fullname=Gargamel
type=evil sorcerer
outputdir=/home/marijn/enemies/gargamel

关于这种格式的规则说明

以分号开头的空行和行将被忽略.

解析此内容的代码遍历文件中的每一行.为了处理评论,他包括了这个表达式

^\s*(;.*)?

据我所知,这个表达式可以从一系列序列开始

空格字符,包括空格,制表符,换页符,换行符和其他Unicode空格

(来源),直到它出现一个分号; 然后是一系列" 除行终止符之外的任何单个字符:\n,\ r,\ u2028或\ u2029. ".所有这些仅限于{0,1}出场.

我没有得到量词的观点？这里.我无法找到(regex101)任何不限制匹配字符串外观的情况都是个问题.为什么表达式与另一个表达式不同:

^\s*(;.*)

提前致谢.