3 ms·
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
by d66 3y ago
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.
- yorwba 3y agoSeems like it should at least be x(|x(|x(|x))) instead of x|xx|xxx|xxxx to avoid quadratic blow-up.
- d66 3y agoyes, that is the actual construction: the disjunction data type only supports a lhs and rhs, so that is the only possible way to represent it. i wrote it the way i did for clarity in the comments.