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

[Brandon Allbery]

On Sat, Sep 17, 2011 at 22:11, Anton Tayanovskyy <
anton.tayanovskyy at gmail.com> wrote:

> 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 ")"
>

The general case for this is solving the Halting Problem, so neither Haskell
nor any other language can do it.  You can disallow infinite values by
encoding the length into the type, but (a) in Haskell this is painful and
(b) runtime values now require runtime types, which you can accommodate but
at the price of reintroducing the problems you are trying to prevent.
 (Dependently typed languages work better for this, but I suspect the result
is rather more draconian than you intend.)

-- 
brandon s allbery                                      allbery.b at gmail.com
wandering unix systems administrator (available)     (412) 475-9364 vm/sms
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110918/cbf28b8e/attachment.htm>