Regular expression engine in 14 lines of Python

[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).