[Haskell-beginners] Empty type

[Brent Yorgey]

On Fri, Oct 25, 2013 at 12:44:06PM +0900, KwangYul Seo wrote:
> Hello,
> 
> It seems there are three different ways to declare an empty type in Haskell.
> 
> http://www.haskell.org/haskellwiki/Empty_type
> 
> 1) data E0 = E0

This one is not empty, as others have pointed out.  It is inhabited by _|_ and E0.

> 2) newtype Void = Void Void

This one is in fact empty (that is, only inhabited by _|_), but it
depends on the fact that newtype constructors do not add any laziness.
The same thing done with 'data',

  data NotVoid = NotVoid NotVoid

is not empty, because it is inhabited by 

_|_, NotVoid _|_, NotVoid (NotVoid _|_), ...

With the data declaration, these are all different.  With the newtype,
they are all equal to _|_.  This is a bit of a technical point,
however; if I were you I wouldn't worry about it at this point.  It
sounds like the most important thing for you to understand is below:

> I'd like to know how the second trick works. Is it possible to create a new
> type from itself? How should I interpret this?

Yes, it is possible to create a new type from itself!  This is called
a "recursive data type", and they are the bread and butter of Haskell
programming.  For some other less silly/trivial examples, consider

  data IntList = Nil | Cons Int IntList

  data BTree a = Empty | Node a (BTree a) (BTree a)

both of which are recursive types.

-Brent