[Haskell-cafe] Musings on type systems
Jacques Carette
carette at mcmaster.ca
Sun Nov 21 22:00:32 EST 2010
On 21/11/2010 8:33 PM, wren ng thornton wrote:
> On 11/20/10 6:33 AM, Ketil Malde wrote:
>> I guess this makes [X] an exponential type, although I don't remember
>> seeing that term :-)
>
> Nope. (a->b) is the exponential type, namely |a->b| = |b|^|a|.
>
> [_] is just a solution to the recursive equation [x] = 1 + x*[x].
So that [X] correspond to the 'type' 1/(1-X). This is sometimes called
the 'asterate' in other contexts, since it corresponds to the Kleene
star. The nice thing about the 'asterate' is that it exists for many
many semi-rings -- and one can use it as a replacement for both 'minus'
and 'exact division' in the Gaussian Elimination algorithm.
Jacques
More information about the Haskell-Cafe
mailing list