# How to detect finite/infinite lists?

Derek Elkins ddarius at hotpop.com
Thu Sep 18 16:53:12 EDT 2003

```On Thu, 18 Sep 2003 20:16:33 +0200
Juanma Barranquero <lektu at terra.es> wrote:

> Extremely-newbie questions:
>
> Is there any way to know if a list is finite or infinite, other than
> doing:
>
>   length l
>
> and waiting forever? :)

In Haskell 98, no.  With a slightly impure extension (observable
sharing) sometimes but in general, no.  The only infinity you need to
recognize is omega and that's just an infinite (cyclic) list of
whatevers. So you -could- use observable sharing for this, but there
isn't much point to it, just use a data structure that says, "an
infinity of x". The simplest thing I would think of is to follow the
arithmetic operation exactly.

data SN
= Zero
| Up
| Down
| SN :+: SN
| SN :*: SN
| SN :^: SN
| Omega SN

omega = Omega Up
iota = Up :+: Omega Down
twoThirds = Omega (Up :+: Down)
twoOmega = Omega Up :+: Omega Up
omegaSquared = Omega Up :*: Omega Up
omegaToTheOmega = Omega Up :^: Omega Up

```