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

[Roman Cheplyaka]

* Anton Tayanovskyy <anton.tayanovskyy at gmail.com> [2011-09-17 22:11:00-0400]
> 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/

Essentially, this is an "infinite" regular expression.
I think it'd be possible to enforce this on the type level. (There was a
thread here some time ago about a type of finite lists.)

If a library can work with such infinite trees, and the user is happy
with resulting performance, then, why not.
For example, this is the case with weighted-regexp library, and also
with the first (and buggy) version of regex-applicative [2].

Otherwise, just let the user know that this function doesn't work with
infinite data structures. Note that in the presence of referential
transparency (i.e. without StableNames or similar tools) it is not
possible to decide at runtime if a value is circular or not.

[2] https://github.com/feuerbach/regex-applicative/commit/95ddfbbfb01c47e292dc7f03069eefe00008907f

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