How to detect finite/infinite lists?

[Brandon Michael Moore]

On Thu, 18 Sep 2003, Juanma Barranquero 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? :)
>
> I ask because I was learning Haskell by writing some pretty naive
> implementation of surreal numbers, where I used lists for left and right
> surreal sets, and I wanted to do some operations on the sets (like
> finding the maximum/minimum), but obviously just on finite sets.
>
> I vaguely suspect the answer is going to be: "No, because lists are lazy
> (at least when they are :) and there's no general way to know beforehand
> how many elements they're going to have". But still, if I write
>
>  x = [1..5]
>
> the compiler knows pretty well x is not going to grow any new member...

Well, it's easy to tell that a list is finite by running length and having
it terminate. This is obviously equivalent to the halting problem so you
can't really expect anything better in general. Why do you need to test
whether lists are infinite? If your lists are being generated from finite
descriptions maybe you could use a data structure that records the
descriptions.

For example, rather than defining
l = [1..]++[2,3..7]
you could define
data EnumList = EnumFromBy Integer Integer
              | EnumFromToBy Int Int Int
              | Append EnumList EnumList
l = EnumFromBy 1 1 `Append` EnumFromToBy 2 1 7

then to test whether a list is infinite you can write
infinite (EnumFromBy _ _) = True
infinite (EnumFromToBy a delta b) = compare a delta == compare a b
infinite (Append l1 l2) = infinite l1 && infinite l2

Of course this only works if it is computable whether a description gives
a finite list.


> (Unrelated) Is there any standard function to do:
>
>  interleave []     _      = []
>  interleave _      []     = []
>  interleave (x:xs) (y:ys) = x : y : interleave xs ys
>
> It's pretty easy to implement as shown or via zipWith, but given that
> Haskell 98 already includes some "basic" functions (like cycle, iterate,
> etc.) I wonder if I've missed this one somehow.
>
> Thanks,

Not as far as I know. The standard List module doesn't define anything
like that and Data.List doesn't define anything like that. What do you
want to use it for? If you are looking for strict alternation you should
use this defintion. If you want a nondeterministic merge as elements are
computed, look at mergeIO in Control.Concurrent in the GHC libraries.

Brandon