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

[Chris Smith]

On Sat, 2011-09-17 at 22:11 -0400, Anton Tayanovskyy 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.

I'm not sure that I understand exactly what the question is... but if
you want to recover the set of values in ML types, you need only add an
'!' before each of the fields of each of your constructors, marking them
as strict fields.  Sadly (but unsurprisingly), this does require using a
different version of lists and other fundamental types as well.

You'll be left with bottom, of course, but in strict-language thinking,
that's nothing but an acknowledgement that a function returning that
type may diverge... something you can't exclude in Haskell *or* ML, it's
just that ML has a different natural way of thinking about it.  That way
lies Agda and Coq.  So you get the next-closest thing: a so-called flat
type, whose values are bottom, and a single layer above it in the
information ordering.

If I've misunderstood the question, my apologies... I haven't actually
been reading this thread.

-- 
Chris Smith