[Haskell-cafe] Basic question concerning data constructors

[Yitzchak Gale]

Andrew Bromage wrote:
> [*] Theoretical nit: It's not technically a "set".
>
> Consider the data type:
>
>      data Foo = Foo (Foo -> Bool)
>
> This declaration states that there's a bijection between the elements of
> Foo and the elements of 2^Foo, which by Cantor's diagonal theorem cannot
> be true for any set.  That's because we only allow computable functions,
> and Foo -> Bool is actually an exponential object in the category Hask.

Data types consist only of computable elements. Since there
are only countably many computable functions, every data type
has at most countably many elements. In particular, it is a set.

The least fixed point under these restrictions is not a bijection
between Foo and 2^Foo. It is only a bijection between Foo and
the subset of computable 2^Foo.

-Yitz