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

51–60 of 127 posts

Re: Calculate the difference and intersection of any two regexes

#51

Post by d66 »

contravariant wrote: post #50
d66 wrote: post #30

Earlier quoted context omitted.

normally you would use an ordinal number [1] to label individual elements of an infinite set while using a cardinal number [2] to measure the size of the set. i believe the cardinality of a set of words from a finite alphabet (with more than one member) is equivalent to the cardinality of the real numbers. this means that the cardinality of .* is c. unfortunately, i don't think that cardinality gets us very far when…

I wouldn't say that's their 'normal' usage, I mean sure you can use them like that but fundamentally ordinal numbers are equivalence classes of ordered sets in the same way that cardinal numbers are equivalence classes of sets. As you've rightly noted the latter equivalence class gets us nothing so throwing away the ordering is a bit of a waste. Of all mathematical concepts 'size' is easily the most subjective so pic…

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.

Re: Calculate the difference and intersection of any two regexes

#53

Post by 082349872349872 »

contravariant wrote: post #9
simlevesque wrote: post #7

Kinda related but I'm looking for something that could give me the number of possible matching strings for a simple regex. Does such a tool exist ?

I feel like it shouldn't be too hard to calculate from the finite automaton that encodes the regular expression, but surely in most cases it will simply be infinite?

see https://www.cs.dartmouth.edu/~doug/nfa.pdf

Re: Calculate the difference and intersection of any two regexes

#57

Post by noduerme »

d66 wrote: post #46
layer8 wrote: post #41

I wanted to see the intersection between syntactically valid URLs and email addresses, but just entering the URL regex (cf. below) already takes too long to process for the page. [\-a-zA-Z0-9@:%._+~#=]{1,256}\.[a-zA-Z0-9()]{1,6}\b([\-a-zA-Z0-9()@:%_+.~#?&//=]*) (source: https://stackoverflow.com/a/3809435/623763 )

expressions like (...){1,256} are very heavyweight and the scala JS code ends up timing out or crashing the browser. if you replace that with (...)+ then it seems to work (at least for me). smaller expressions like (...){1,6} should be fine.

Just wondering, what is it about testing repetition [a-z]{1,256} with an upper bound that's so heavy? Intuitively it feels like greedy testing [a-z]+ should actually be worse since it has to work back from the end of the input.

Re: Calculate the difference and intersection of any two regexes

#58

Post by 1-more »

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…

In languages with tagged union types you do this a lot! Some Haskell pseudocode for ya

    module Email (Address, fromText, toText) where -- note we do not export the constructor of Address, just the type

    data Address = Address Text

    fromString :: Text -> Maybe Address
    fromString =
        -- you'd do your validation in here and return Nothing if it's a bad address.
        -- Signal validity out of band, not in band with the data.

    toText :: Address -> Text
    toText (Address addr) = addr -- for when you need to output it somewhere

Re: Calculate the difference and intersection of any two regexes

#59

Post by d66 »

noduerme wrote: post #57
d66 wrote: post #46

Earlier quoted context omitted.

expressions like (...){1,256} are very heavyweight and the scala JS code ends up timing out or crashing the browser. if you replace that with (...)+ then it seems to work (at least for me). smaller expressions like (...){1,6} should be fine.

Just wondering, what is it about testing repetition [a-z]{1,256} with an upper bound that's so heavy? Intuitively it feels like greedy testing [a-z]+ should actually be worse since it has to work back from the end of the input.

the library uses a fairly simple data representation where x{m,n} is compiled using conjunction and disjunction. so x{1,4} ends up being represented as x|xx|xxx|xxxx.

this simplifies the code for testing equality and inclusion, since logically x{n} is just xx... (n times) and x{m,n} is just x{m}|x{m+1}|...|x{n}.

but when you have x{m,n} and n-m is large you can imagine what kind of problems that causes.

Re: Calculate the difference and intersection of any two regexes

#60

Post by [deleted] »

dhosek wrote: post #35
klysm wrote: post #12

Regular expressions are a great example of bundling up some really neat and complex mathematical theory into a valuable interface. Linear algebra feels similar to me.

It always amazes me how given the appropriate field, so much math can be transformed into linear algebra. Even Möbius transformations on the complex plane w=(az+b)/(cz+d) can be turned into linear algebra.

[deleted]
Post reply on HN