Infinite types
camarao at dcc.ufmg.br
camarao at dcc.ufmg.br
Sat Dec 6 13:30:13 EST 2003
> 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
>
More information about the Haskell-Cafe
mailing list