RE#: how we built the fastest regex engine in F# • Hacker News Board

Re: RE#: how we built the fastest regex engine in F#

#11

Post by gbacon » Wed, Mar 04, 2026, 12:09 PM UTC

That’s beautiful work. Check out other examples in the interactive web app:

https://ieviev.github.io/resharp-webapp/

Back in the Usenet days, questions came up all the time about matching substrings that do not contain whatever. It’s technically possible without an explicit NOT operator because regular languages are closed under complement — along with union, intersection, Kleene star, etc. — but a bear to get right by hand for even simple cases.

Unbounded lookarounds without performance penalty at search time are an exciting feature too.

Re: RE#: how we built the fastest regex engine in F#

#12

Post by ieviev » Wed, Mar 04, 2026, 12:14 PM UTC

anentropic wrote: post #6

Fantastic stuff! FYI some code snippets are unreadable in 'light mode' ("what substrings does the regex (a|ab)+ match in the following input?")

ah thank you for letting me know, fixed it now!

Re: RE#: how we built the fastest regex engine in F#

#13

Post by pjmlp » Wed, Mar 04, 2026, 12:16 PM UTC

raincole wrote: post #3

sourcegrift wrote: post #2

I've had nothing but great experience with F#. If it wasn't associated with Microsoft, it'd be more popular than haskell

I think if it weren't a 'first class' member of .NET ecosystem[0], no one would know F#. After all Haskell and Ocaml already exist. [0]: my very charitable take, as MS obviously cares C# much much more than F#.

Management has always behaved as if they repent having added F# to VS 2010, at least it hasn't yet suffered the same stagnation as VB, even C++/CLI was updated to C++20 (minus modules).

In any case, those of us that don't have issues with .NET, or Java (also cool to hate these days), get to play with F# and Scala, and feel no need to be amazed with Rust's type system inherited from ML languages.

It is yet another "Rust but with GC" that every couple of months pops up in some forums.

Re: RE#: how we built the fastest regex engine in F#

#14

Post by agnishom » Wed, Mar 04, 2026, 12:22 PM UTC

The author mentions that they found Mamouras et al. (POPL 2024), but not the associated implementation. While the Rust implementation is not public, a Haskell implementation can be found here: https://github.com/Agnishom/lregex

Re: RE#: how we built the fastest regex engine in F#

#15

Post by andriamanitra » Wed, Mar 04, 2026, 12:27 PM UTC

This is very interesting. I'm a bit skeptical about the benchmarks / performance claims because they seem almost too good to be true but even just the extended operators alone are a nice improvement over existing regex engines.

The post mentions they also have a native library implemented in Rust without dependencies but I couldn't find a link to it. Is that available somewhere? I would love to try it out in some of my projects but I don't use .NET so the NuGET package is of no use to me.

Re: RE#: how we built the fastest regex engine in F#

#16

Post by noelwelsh » Wed, Mar 04, 2026, 12:28 PM UTC

I love regular expression derivatives. One neat thing about regular expression derivatives is they are continuation-passing style for regular expressions. The derivative is "what to do next" after seeing a character, which is the continuation of the re. It's a nice conceptual connection if you're into programming language theory.

Low-key hate the lack of capitalization on the blog, which made me stumble over every sentence start. Great blog post a bit marred by unnecessary divergence from standard written English.

Re: RE#: how we built the fastest regex engine in F#

#17

Post by brabel » Wed, Mar 04, 2026, 12:34 PM UTC

dude250711 wrote: post #5

sourcegrift wrote: post #2

I've had nothing but great experience with F#. If it wasn't associated with Microsoft, it'd be more popular than haskell

> ...it'd be more popular than haskell https://steve-yegge.blogspot.com/2010/12/haskell-researchers...

Did they ever get the full extra person who gives a shit?

Re: RE#: how we built the fastest regex engine in F#

#18

Post by [deleted] » Wed, Mar 04, 2026, 12:58 PM UTC

pjmlp wrote: post #13

raincole wrote: post #3

Earlier quoted context omitted.

I think if it weren't a 'first class' member of .NET ecosystem[0], no one would know F#. After all Haskell and Ocaml already exist. [0]: my very charitable take, as MS obviously cares C# much much more than F#.

Management has always behaved as if they repent having added F# to VS 2010, at least it hasn't yet suffered the same stagnation as VB, even C++/CLI was updated to C++20 (minus modules). In any case, those of us that don't have issues with .NET, or Java (also cool to hate these days), get to play with F# and Scala, and feel no need to be amazed with Rust's type system inherited from ML languages. It is yet another "Ru…

[deleted]

Re: RE#: how we built the fastest regex engine in F#

#19

Post by meindnoch » Wed, Mar 04, 2026, 12:59 PM UTC

@burnsushi is that true?

Re: RE#: how we built the fastest regex engine in F#

#20

Post by masfuerte » Wed, Mar 04, 2026, 1:05 PM UTC

This is very impressive.

> how does RE# find the leftmost-longest match efficiently? remember the bidirectional scanning we mentioned earlier - run the DFA right to left to find all possible match starts, then run a reversed DFA left to right to find the ends. the leftmost start paired with the rightmost end gives you leftmost-longest. two linear DFA scans, no backtracking, no ambiguity.

I'm pretty sure that should say "the leftmost start paired with the leftmost end".

This also implies that the algorithm has to scan the entire input to find the first match, and the article goes on to confirm this. So the algorithm is a poor choice if you just want the first match in a very long text. But if you want all matches it is very good.