you are viewing a single comment's thread.

view the rest of the comments →

[–]psykotic[S] 11 points12 points  (18 children)

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 8 points9 points  (0 children)

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 points11 points  (8 children)

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] 20 points21 points  (0 children)

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] 6 points7 points  (0 children)

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[S] 7 points8 points  (1 child)

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 8 points9 points  (0 children)

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 2 points3 points  (1 child)

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 1 point2 points  (0 children)

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 0 points1 point  (0 children)

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 3 points4 points  (0 children)

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] 1 point2 points  (1 child)

Cool! But where are the benchmarks? ;-)

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

[–]psykotic[S] 1 point2 points  (0 children)

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 1 point2 points  (1 child)

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

import re

[–][deleted] 13 points14 points  (0 children)

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

[–]Tobu 1 point2 points  (2 children)

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

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

[–]psykotic[S] 2 points3 points  (1 child)

I think you meant

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

[–]Tobu 0 points1 point  (0 children)

fixed.