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

[Anton Tayanovskyy]

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
<anton.tayanovskyy at gmail.com> 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 <roma at ro-che.info> 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 at 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