Re: [Haskell-cafe] regex-applicative library needs your help! (algorithmic challenge)

By the way, can Haskell have a type that admits regular expression and only those? I mostly do ML these days, so trying to write up a regex types in Haskell I was unpleasantly surprised to discover that there are all sorts of exotic terms inhabiting it, which I did not have to worry about in ML. Besides `undefined` you can have for terms that try to define a grammar with nested parentheses. Using regex-applicative syntax: expr = ... <|> pure (\ _ x _ -> x) <*> sym "(" <*> expr <*> sym ")" Is this the so-called 'paucity of types' [1]? What do you do, as a library designer? Return bottom or try to detect and error out for these kind of values? Thanks, A [1] http://existentialtype.wordpress.com/tag/recursion/ On Sat, Sep 17, 2011 at 9:46 PM, Anton Tayanovskyy wrote:

So you want to encode priorities efficiently as far as I understand from [1]? Could bit-packing combined with prefix elimination do the trick? Choice boils down to binary choice. Attach a number N to every execution thread that sits in a given NFA state. When the thread moves through a binary choice state, it splits into two threads with N_{left} = 2 * N + 1 and N_{right} = 2 * N. When two threads arrive at the same NFA state, the machine picks one with greater N and discards the other, thus giving priority to early over late and left over right. This makes these numbers grow quickly, but at any point in the simulation one can identify the common binary prefix of all the thread numbers and remove it, because it will not be relevant for comparison. If this is too costly, amortize and do it every K steps instead of on every step.

Anton

[1] https://github.com/feuerbach/regex-applicative/wiki/Call-For-Help

On Tue, Sep 13, 2011 at 1:40 AM, Roman Cheplyaka wrote:

...

Please help make the regex-based parsing library efficient!

https://github.com/feuerbach/regex-applicative/wiki/Call-For-Help

-- Roman I. Cheplyaka :: http://ro-che.info/

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Kind Regards, Anton Tayanovskyy

WebSharper™ - type-safe JavaScript in F# http://intellifactory.com

-- Kind Regards, Anton Tayanovskyy WebSharper™ - type-safe JavaScript in F# http://intellifactory.com