Stack Overflow
Stack Overflow

Questions tagged [quantifiers]

In logic, quantification is the binding of a variable ranging over a domain. The variable thereby becomes bound by an operator called a quantifier.

In logic, quantification is the binding of a variable ranging over a domain. The variable thereby becomes bound by an operator called a quantifier.

The two fundamental kinds of quantification in predicate logic are universal quantification and existential quantification.

233 questions
105
votes
5 answers

Regex expressions in Java, \\s vs. \\s+

What's the difference between the following two expressions? x = x.replaceAll("\\s", ""); x = x.replaceAll("\\s+", "");
mpluse
  • 1,857
  • 6
  • 18
  • 25
70
votes
3 answers

What's the theoretical basis for existential types?

The Haskell Wiki does a good job of explaining how to use existential types, but I don't quite grok the theory behind them. Consider this example of an existential type: data S = forall a. Show a => S a -- (1) to define a type wrapper for…
Chris Taylor
  • 46,912
  • 15
  • 110
  • 154
34
votes
4 answers

What does "exists" mean in Haskell type system?

I'm struggling to understand the exists keyword in relation to Haskell type system. As far as I know, there is no such keyword in Haskell by default, but: There are extensions which add them, in declarations like these data Accum a = exists s.…
Valentin Golev
  • 9,965
  • 10
  • 60
  • 84
28
votes
1 answer

Scoped type variables require explicit foralls. Why?

If you want to use GHC's lexically scoped type variables, you also have to use explicit universal quantification. That is, you have to add forall declarations to your functions' type signatures: {-# LANGUAGE ExplicitForAll, ScopedTypeVariables…
pash
  • 1,657
  • 1
  • 14
  • 29
19
votes
2 answers

Emulating possessive quantifiers

Is it possible to emulate possessive quantifiers (.NET doesn’t support it) using atomic grouping (or in other way)? Note. I found that (x+x+)++y can be replaced with (?>(x+x+)+)y, but this is just an example and I don’t know whether always…
LukeSw
  • 661
  • 3
  • 13
13
votes
2 answers

Understanding Quantifiers

I was going through the Java Tutorial on Quantifiers. There is a difference mentioned among Differences Among Greedy, Reluctant, and Possessive Quantifiers. I am not able to understand what's the difference exactly. Explanation provided as…
xyz
  • 2,160
  • 3
  • 20
  • 31
12
votes
3 answers

Alternative to possessive quantifier in python

I am trying to match all occurences of the String Article followed by a number (single or more digits) which are not followed by an opening parentheses. In Sublime Text, I am using the following regex: Article\s[0-9]++(?!\() to search the following…
user
  • 123
  • 1
  • 5
12
votes
1 answer

Closures and universal quantification

I've been trying to work out how to implement Church-encoded data types in Scala. It seems that it requires rank-n types since you would need a first-class const function of type forAll a. a -> (forAll b. b -> b). However, I was able to encode pairs…
Apocalisp
  • 34,834
  • 8
  • 106
  • 155
11
votes
2 answers

JavaScript: Invalid quantifier in regex

The regex is constructed on the fly, but I've output it to firebug: (.{1,38})(+|$\n?) the error is invalid quantifier +|$\n?) I'm not sure where to start. The actual code is: var re = top.RegExp; var regex = new re("(.{1," + len + "})(+|$\\n?)",…
Stephen
  • 18,827
  • 9
  • 60
  • 98
11
votes
1 answer

Is it valid to lift positive positive forall quantifiers to the outside?

This question came up in discussion on #haskell. Is it always correct to lift a deeply nested forall to the top, if its occurrence is positive? E.g: ((forall a. P(a)) -> S) -> T (where P, S, T are to be understood as metavariables) to forall a.…
drquicksilver
  • 1,627
  • 9
  • 12
10
votes
1 answer

universal and existential quantifier in prolog

How can I implement following rules in prolog. I write the “ No spiders are mammals” sentence as Existential and universal: ¬∃x(mammals(X) ∧ spider(X) ) //It is not the case that mammals are spider ∀X(mammals(X) ⇒ ¬spider(X)) //All mammals are…
user2064809
  • 403
  • 1
  • 4
  • 13
10
votes
2 answers

Capturing Quantifiers and Quantifier Arithmetic

At the outset, let me explain that this question is neither about how to capture groups, nor about how to use quantifiers, two features of regex I am perfectly familiar with. It is more of an advanced question for regex lovers who may be familiar…
zx81
  • 41,100
  • 9
  • 89
  • 105
9
votes
2 answers

What's the difference between this two regular expressions? (Understanding ? Quantifier)

On book Eloquent JavaScript chapter 9: Regular Expressions under Section "Parsing an INI File" there's an example which includes a regular expression I don't catch at all. The author is trying to parse next…
Noob_Number_1
  • 725
  • 5
  • 20
8
votes
1 answer

Why do I get different backtracking with these Raku regexes?

I'm getting unexpected backtracking of the + quantifier of a Raku regex. In this regex: 'abc' ~~ m/(\w+) {say $0} /; say $0; I get the expected result: ｢abc｣ # inner say ｢ab｣ # inner say ｢ab｣ # final say That…
Julio
  • 5,208
  • 1
  • 13
  • 42
5
votes
1 answer

Why do lazy quantifiers become greedy when followed by a question mark?

Why is it that "hello".match(/^(.*?)?/)[0] evaluates to "h" rather than to ""? Put another way, why does following a lazy expression (.*?) with a zero-or-one quantifier ? make it a little greedy?
user541686
  • 205,094
  • 128
  • 528
  • 886
1
2 3
…
15 16