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
More information about the Haskell-Cafe
mailing list