25

Possible Duplicate:
How to tell if a list is infinite?

In Haskell, you can define an infinite list, for example [1..]. Is there a built-in function in Haskell to recognize whether a list has finite length? I don't imagine it is possible to write a user-supplied function to do this, but the internal representation of lists by Haskell may be able to support it. If not in standard Haskell, is there an extension providing such a feature?

Community
  • 1
  • 1
quant_dev
  • 6,181
  • 1
  • 34
  • 57
  • 2
    I don't think so. Because of lazy evaluation the Haskell runtime really doesn't know whether the list will be infinite; it's not that it just doesn't expose it to the program. – Mechanical snail Mar 27 '12 at 12:20
  • 12
    I strongly suspect this is equivalent to the so called 'halting problem', in which case the answer would be "No". – Daniel Pratt Mar 27 '12 at 12:22
  • If you wish to be able to recognize infinite structures, you could read something about coinduction: http://en.wikipedia.org/wiki/Coinduction, http://www.disi.unige.it/dottorato/corsi/DPCI2011/ – Riccardo T. Mar 27 '12 at 12:32
  • 3
    Here's a function that never gives a wrong answer: `isInfinite list = case list of [] -> False; _:rest -> isInfinite rest` – Vitus Mar 27 '12 at 16:04
  • 1
    There is no "internal representation" since lists are just ADTs like everything else – alternative Mar 27 '12 at 19:08

5 Answers5

40

No, this is not possible. It would be impossible to write such a function, because you can have lists whose finiteness might be unknown: consider a recursive loop generating a list of all the twin primes it can find. Or, to follow up on what Daniel Pratt mentioned in the comments, you could have a list of all the steps a universal Turing machine takes during its execution, ending the list when the machine halts. Then, you could simply check whether such a list is infinite, and solve the Halting problem!

The only question an implementation could answer is whether a list is cyclic: if one of its tail pointers points back to a previous cell of the list. However, this is implementation-specific (Haskell doesn't specify anything about how implementations must represent values), impure (different ways of writing the same list would give different answers), and even dependent on things like whether the list you pass in to such a function has been evaluated yet. Even then, it still wouldn't be able to distinguish finite lists from infinite lists in the general case!

(I mention this because, in many languages (such as members of the Lisp family), cyclic lists are the only kind of infinite lists; there's no way to express something like "a list of all integers". So, in those languages, you can check whether a list is finite or not.)

ehird
  • 40,602
  • 3
  • 180
  • 182
  • 3
    For checking whether a list is cyclic, check out [vacuum](http://hackage.haskell.org/package/vacuum), which can return a graph of the heap layout of a Haskell value which you can then check for cycles. However, this is both GHC-specific and impure as indicated above. – hammar Mar 27 '12 at 12:56
  • The (in)finitude of twin primes isn't known to be undecidable; so far, answering the question is just really, really, really, really hard. – jwodder Mar 27 '12 at 15:57
  • @jwodder: Yeah, that was bad phrasing. I've edited my answer. – ehird Mar 27 '12 at 16:19
  • (deleted previous comment, didn't read Q close enough). Actually, any decent Lisp is perfectly capable of implementing lazy indefinite lists and thus expressing something like "a list of all integers", with finite lists with a generator expression in their tail. List data object itself would be finite of course, but it would express an infinite list abstraction. This situation wouldn't be at all different from Haskell *implementation* I imagine. – Will Ness Mar 27 '12 at 18:14
6

There isn't any way to test for finiteness of lists other than iterating over the list to search for the final [] in any implementation I'm aware of. And in general, it is impossible to tell whether a list is finite or infinite without actually going to look for the end (which of course means that every time you get an answer, that says finite).

Daniel Fischer
  • 181,706
  • 17
  • 308
  • 431
6

You could write a wrapper type around list which keeps track of infiniteness, and limit yourself to "decidable" operations only (somehow similar to NonEmpty, which avoids empty lists):

import Control.Applicative

data List a = List (Maybe Int) [a]

infiniteList (List Nothing _) = true
infiniteList _ = false

emptyList = List (Just 0) []
singletonList x = List (Just 1) [x]
cycleList xs = List Nothing (cycle xs)
numbersFromList n = List Nothing [n..] 
appendList (List sx xs)  (List sy ys) = List ((+) <$> sx <*> sy) (xs ++ ys)
tailList (List s xs) = List (fmap pred s) (tail xs)
...
Landei
  • 54,104
  • 13
  • 100
  • 195
  • What's the advantage of actually storing the length, wouldn't a simple `Bool` do? After all, for a finite list it's redundant. – leftaroundabout Mar 27 '12 at 14:30
  • 1
    `Bool` would do as well, but basically we want to be able to find out "how long" our list is, so why not exploiting the additional argument, especially as `length` is slow for long lists? – Landei Mar 27 '12 at 14:38
3

As ehird wrote, your only hope is in finding out whether a list is cyclic. A way of doing so is to use an extension to Haskell called "observable sharing". See for instance: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.4053

Jan-Willem
  • 187
  • 1
  • 12
1

When talking about "internal representation of lists", from standpoint of Haskell implementation, there are no infinite lists. The "list" you ask about is actually a description of computational process, not a data object. No data object is infinite inside a computer. Such a thing simply does not exist.

As others have told you, internal list data might be cyclical, and implementation usually would be able to detect this, having a concept of pointer equality. But Haskell itself has no such concept.

Here's a Common Lisp function to detect the cyclicity of a list. cdr advances along a list by one notch, and cddr - by two. eq is a pointer equality predicate.

(defun is-cyclical (p)
  (labels ((go (p q) 
             (if (not (null q)) 
               (if (eq p q) t 
                 (go (cdr p) (cddr q))))))
    (go p (cdr p))))
Will Ness
  • 70,110
  • 9
  • 98
  • 181