[Haskell-cafe] Musings on type systems

[wren ng thornton]

On 11/20/10 6:33 AM, Ketil Malde wrote:
> Andrew Coppin<andrewcoppin at btinternet.com>  writes:
>
>> Now here's an interesting thought. Haskell has "algebraic data
>> types". "Algebraic" because they are sum types of product types (or,
>> equivilently, product types of sum types). Now I don't actually know
>> what those terms mean,
>
> The quick rule to remember this that the size of the resulting types
> correspond to the arithmetic names.  I.e.
>
>   data Sum a b = A a | B b -- values = values in a + values in b
>   data Prod a b = P a b    -- values = values in a * values in b
>
> 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].

-- 
Live well,
~wren