Infinite types

[camarao at dcc.ufmg.br]

> Say I have the following function, ... :
>
>     f n () = (n, f (n + 1))
> ...
> I have two questions:
>
> 1.  How can I tell from the Haskell 98 Revised Report that this
>     function isn't allowed?  The discussions of typing in the Report
>     generally defer to the ``standard Hindley-Milner analysis.''

In your example, if we assume that "f" has type, say, "a->()->(a,b)", for
some "a","b", then it is used, in its own definition, with type
"a->()->b".

In the Hindley-Damas/Milner type system, there is no "polymorphic
recursion": a variable being defined may not be used polymorphically
inside
its own definition. In other words, for typing its own definition, a
variable is assumed to have a simple (non-quantified) type.

Even in the Milner-Mycroft type system, where we have polymorphic
recursion (a variable may be used polymorphically in its own definition),
this expression could not be typed, because (informally speaking) a
polymorphic type may only be instantiated, and "a->()->b" is not (cannot
be) an instance of "a->()->(a,b)", for any "a","b".

Hope that helps. Cheers,

Carlos











>     Is this really enough to tell that the function isn't well-typed
>     in Haskell?  I concede that I haven't read the cited Hindley and
>     Damas/Milner papers, but it seems like there might be more to
>     say about what is and isn't allowed.
>
> 2.  Is there by chance a compiler option for ghc that causes the
>     restriction to be dropped?
>
> I don't need this kind of function for anything practical (and I
> realize I can get an equivalent effect with an algebraic datatype).
> I'm just trying to figure out what typing restrictions (if any) are
> implicitly assumed in the Report.  (Generally, this is the kind of
> stuff I don't know, as a relative newcomer to fp.)
>
> Regards,
>
> Jeff Scofield (PhD)
> Seattle
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>