[Haskell-beginners] Empty type

[Nicholas Vanderweit]

Not sure if this is haskell-beginners material, but it's possible in a lazy
language like Haskell to define an inhabitant of NotVoid recursively:

let x = NotVoid x in x

Or, alternatively, using fix from Data.Function:

fix NotVoid


This gives NotVoid (NotVoid (NotVoid (...)))


Nick



On Fri, Oct 25, 2013 at 5:54 AM, Brent Yorgey <byorgey at seas.upenn.edu>wrote:

> 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
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20131025/612c0d2d/attachment.html>