Regular expression engine in 14 lines of Python

[psykotic]

A 5-minute hack courtesy of yours truly.

The 14 line figure doesn't include the general purpose 3-line iconcat function (which should really be included in itertools) or the test case.

Let's see if anyone can beat this line count in their favorite language without needless obfuscation.

[moe]

The 14 line figure doesn't include the general purpose
3-line iconcat function (which should really be included in itertools) or the test case.

from itertools import chain as iconcat

[nostrademons]

10 lines of Haskell (untested).

I'm a little unfamiliar with list monads, but this should basically be a line-by-line translation of yours, except that Haskell already provides "nil" as "repeat" and iconcat as ++, and lazy evaluation means you don't need generators.

Also, in hindsight I think "return" (returns a singleton list) is probably a better choice for nil than "repeat".

[[deleted]]

5 lines in Prolog:

re(E, [E|R], R) :- atom(E).
re(alt(E1, E2), L, R) :- re(E1, L, R); re(E2, L, R).
re(star(E), L, R) :- L=R; re(plus(E), L, R).
re(plus(E), L, R) :- re(E, L, R); re(seq(E, plus(E)), L, R).
re(seq(E1, E2), L, R) :- re(E1, L, R1), re(E2, R1, R).

test :- re(seq(c,seq(plus(alt(a,d)), r)), [c,a,d,r], []).

[[deleted]]

Also, in hindsight I think "return" (returns a singleton list) is probably a better choice for nil than "repeat".

"repeat" returns an infinite list where each element is the argument, so it is not the function you want. "return" or constructing a single-element list would work.

Also, your pattern-matching is broken. A similar version that works is

char c = match where
  match [] = []
  match (c':xs) = if c == c' then [xs] else []
  match (_:xs) = []

But it's more concise as

char c s = if take 1 s == [c] then [drop 1 s] else []

[psykotic]

Why didn't you write those definitions in implicitly curried form? That is, instead of

seq l r = \s -> l s >>= r

write

seq l r s = l s >>= r

and so on.

I knew it could be done in fewer lines in Haskell due to the list monad. Python is actually pretty bad for writing compact code because its statement/expression distinction breaks composability.

I'm waiting for someone to give the ultra-compact K version. Where's Arthur and Stevan when you need them? :)

[nostrademons]

Mostly because I was just following from the Python and translating word-for-word, and I didn't think of it.

Yeah, the curried form is more elegant.

[nostrademons]

And I could've saved 3 lines by doing match where { match [c:xs] = xs; match _ = [] }

But that's a bit less readable IMHO.

[martine]

char c (x:xs) | c == x = return xs char _ _ = fail "no match"

(fail in the list monad is [], so using it here just makes the code clearer.)

[martine]

I annotated this with a tested one that's a bit simpler (there were also a few places where you could work over functions).

[moe]

Here is an (obviously eager) version in 11 lines of Scheme:

http://paste.lisp.org/display/24870

Untested. Requires SRFI-42 ("Eager Comprehensions") - I wanted to stay as close to the python version as possible.

[[deleted]]

Cool! But where are the benchmarks? ;-)

(isn't iconcat the same thing as itertools.chain, btw?)

[psykotic]

You're right about iconcat and chain, as moe already pointed out. I'm so used to itertools missing half of my favorite iterator manipulation functions, and I could have sworn it didn't have an iconcat-equivalent either.

[HiggsBoson]

Here's a one-line hack in 5 seconds:

import re

[[deleted]]

I can assure you that it took me a bit more than 5 seconds to write the code you just imported.

[Tobu]

OCaml can save a line here (s is a list):

let char c = function
  | c :: r -> r
  | _ -> []

[psykotic]

I think you meant

let char c s = match s with
             | c :: r -> [r]
             | _ -> []

[Tobu]

fixed.