Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Calculate the difference and intersection of any two regexes

phylactery.org

Post reply on HN
Print view View original

111–120 of 127 posts

Re: Calculate the difference and intersection of any two regexes

#111

Post by usrusr »

oever wrote: post #40

This library can be used to create string class hierarchies. That, in turn, can help to use typed strings more. For example, e-mails and urls are a special syntax. Their value space is a subset of all non-empty string which is a subset of all strings. An e-mail address could be passed into a function that requires a non-empty string as input. When the type-system knows that an e-mail string is a subclass of non-empty…

Nothing like a dive into the wondrous world of what is and isn't allowed in an email address left of the @ on a warm late-summer morning. It's one of the mysteries of the modern world. The simple heuristic that proposes that every regex trying to express "valid email address" is wrong is a sufficiently safe bet, but it ruins all the fun.

Re: Calculate the difference and intersection of any two regexes

#112

Post by contravariant »

contravariant wrote: post #80
d66 wrote: post #51

Earlier quoted context omitted.

interesting! what would [ab]* be? for computing an ordinal number the only real difficulty is how to handle kleene star: given ord(X) how do we calculate ord(X*)? but as you probably noticed i'm a bit out of my depth when dealing with ordinals.

Unless I'm very mistaken adding onto the end of a string doesn't affect lexicographic order, so that's effectively [ab]*. The ordinality of [ab] is simple, it's 2, but the kleene star is a bit of an odd one, it's not quite exponentiation. To reason about the kleene star it's a bit simpler to consider something like R^*n, where you repeat up to n times. Obviously R^*0 = 1 and R^*S(n) can be built from R^*n by picking…

Hmm, turns out this fails to be an ordinal because regular languages aren't well-ordered (except if you reverse the lexicographic order, maybe?). They are what is called an order type, and it looks like it should be possible to identify them with subsets of the rationals, if you wanted to.

Perhaps reversing the lexicographic order makes more sense, in that case longer tuples simply order last so R^* = 1 + R + R^2 + ..., the limit here is much easier since R^*n = 1 + R + ... + R^n is downwards closed as a subset of R^*S(n).

Then again in that scenario [ab]* is simply ω because it is effectively the same as just writing an integer in binary, so it is less interesting in a way.

Re: Calculate the difference and intersection of any two regexes

#113

Post by [deleted] »

usrusr wrote: post #111
oever wrote: post #40

This library can be used to create string class hierarchies. That, in turn, can help to use typed strings more. For example, e-mails and urls are a special syntax. Their value space is a subset of all non-empty string which is a subset of all strings. An e-mail address could be passed into a function that requires a non-empty string as input. When the type-system knows that an e-mail string is a subclass of non-empty…

Nothing like a dive into the wondrous world of what is and isn't allowed in an email address left of the @ on a warm late-summer morning. It's one of the mysteries of the modern world. The simple heuristic that proposes that every regex trying to express "valid email address" is wrong is a sufficiently safe bet, but it ruins all the fun.

[deleted]

Re: Calculate the difference and intersection of any two regexes

#114

Post by rntz »

rntz wrote: post #85
sebzim4500 wrote: post #83

Earlier quoted context omitted.

Surely that fails for e.g. a?a?a?. I'd imagine you could do some sort of simplification first though to avoid this redundancy.

You're correct, and I don't see any good way to avoid this that doesn't involve enumerating the actual language (at least when the language is finite). Oof, my hubris.

It turns out to be not that hard to just compute the language of the regex, if it is finite, and otherwise note that it is infinite:

    import Prelude hiding (null)
    import Data.Set (Set, toList, fromList, empty, singleton, isSubsetOf, unions, null)

    data Regex = Class [Char]   -- character class
               | Seq [Regex]    -- sequence, ABC
               | Choice [Regex] -- choice, A|B|C
               | Star Regex     -- zero or more, A*
                 deriving (Show)

    -- The language of a regex is either finite or infinite.
    -- We only care about the finite case.
    data Lang = Finite (Set String) | Infinite deriving (Show, Eq)

    zero = Finite empty
    one = Finite (singleton "")

    isEmpty (Finite s) = null s
    isEmpty Infinite = False

    cat :: Lang -> Lang -> Lang
    cat x y | isEmpty x || isEmpty y = zero
    cat (Finite s) (Finite t) = Finite $ fromList [x ++ y | x  Bool
    subsingleton Infinite = False
    subsingleton (Finite s) = isSubsetOf s (fromList [""])

    eval :: Regex -> Lang
    eval (Class chars) = Finite $ fromList [[c] | c

Re: Calculate the difference and intersection of any two regexes

#115

Post by avgcorrection »

eru wrote: post #90
School-Cotton wrote: post #81

Earlier quoted context omitted.

People are downvoting you because quirky/jokey super-colloquial language like “wossis mean? TIA” is hard to understand, and also just doesn’t really mesh with the vibe of the site.

What does TIA even mean?

That Is Amazing.

Re: Calculate the difference and intersection of any two regexes

#116

Post by zeroimpl »

wizofaus wrote: post #103
zeroimpl wrote: post #98

Earlier quoted context omitted.

Only when the ^ or $ were at the start/end of your string is it simple. Eg: (a|b|^)(c|d|^)foo Rewriting without ^ can require much longer regex.

Isn't that just ((a|b)?(c|d)|c|d)?foo Unless you mean it as a search expression, in which case it's more like ((.*a|.*b)(c|d)|c|d)?foo Which I have to admit was a lot harder to figure out than I thought it would be (and may not even be right!)

Yeah the latter.

In an engine supporting ^ and $, searching for this

    (a|b|^)(c|d|^)foo
is equivalent to searching for this

    ^((.*a|.*b)(c|d)|c|d)?foo.*$
And in this context you can drop the leading/trailing ^/$ since they are implicit.

Re: Calculate the difference and intersection of any two regexes

#117

Post by croes »

oever wrote: post #40

This library can be used to create string class hierarchies. That, in turn, can help to use typed strings more. For example, e-mails and urls are a special syntax. Their value space is a subset of all non-empty string which is a subset of all strings. An e-mail address could be passed into a function that requires a non-empty string as input. When the type-system knows that an e-mail string is a subclass of non-empty…

>An e-mail address could be passed into a function that requires a non-empty string as input. When the type-system knows that an e-mail string is a subclass of non-empty string, it knows that an email address is valid.

Don't use regex for email address validation

https://news.ycombinator.com/item?id=31092912

Re: Calculate the difference and intersection of any two regexes

#118

Post by 1-more »

alexvitkov wrote: post #104
1-more wrote: post #102

Earlier quoted context omitted.

Haha sorry, I get those backwards a lot. I was gonna do elm but then it’d be a conversation about why we’re writing our own email address validation on the front end instead of using the platform.

Don't worry, that's normal -- in this forum we only talk about how good obscure languages are, nobody actually uses Haskell.

I figure you're joshing but I literally write it for work (although I haven't been in our haskell codebase in months, tragically). I just have a particularly smooth brain so I forget all the little differences as soon as I'm done. Always in exams mode.

Re: Calculate the difference and intersection of any two regexes

#119

Post by DannyBee »

DannyBee wrote: post #86
less_less wrote: post #49

Interesting. I think this problem is actually EXPSPACE-complete in general? But still has a straightforward algorithm. https://en.wikipedia.org/wiki/EXPSPACE

It depends on your operators. For these, no. Equivalence of DFA or NFA is PSPACE complete by savitch's theorem, regardless of time bound. As such, most types of regex equivalence is pspace-complete. https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.... Has a detailed breakdown of operators vs complexity. In particular, the paper cited in the expspace page is talking about allowing a squaring operator. It is…

Since this may be confusing at first (why does squaring buy you anything here) - the reason squaring makes it expspace complete is, basically, squaring allows you to express an exponentially large regex in less than exponential input size.

This in turn means polynomial space in the size of the input is no longer enough to deal with the regex.

If you only allow repetition, than an exponentially large regex requires exponential input size, and thus polynomial space in the size of the input still suffices to do equivalence.

This is generally true - operators that allow you to reduce the size of the input necessary to express a regex by a complexity class will usually increase the size complexity class necessary to determine equivalence by a corresponding amount.

Re: Calculate the difference and intersection of any two regexes

#120

Post by zamadatix »

est wrote: post #101

Ha, trying to paste "regex filter numbers divisible by 3" and the page froze to death https://stackoverflow.com/q/10992279/41948 ^(?:[0369]+|[147](?:[0369]*[147][0369]*[258])*(?:[0369]*[258]|[0369]*[147][0369]*[147])|[258](?:[0369]*[258][0369]*[147])*(?:[0369]*[147]|[0369]*[258][0369]*[258]))+$ ^([0369]|[147][0369]*[258]|(([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]\*[258])))+$ I wonder if t…

The page says it doesn't support anchors anyway.
Post reply on HN