How to detect finite/infinite lists?

[Derek Elkins]

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