Is the infinite list capacity built into the `Ord` typeclass, or a product of haskell's definition of a number?

Question

I'm trying to wrap my head around how haskell achieves infinite lists... here's my road block:

You have a list of type A, and A implements the Ord typeclass. You can describe a span of ordered elements like so (intergers, for example):

[1..6]

which equates to...

Cons 1 (Cons 2 (Cons 3 (Cons 4 (Cons 5 (Cons 6 (Empty))))))

How would haskell know how to construct an infinite list? Would haskell be able to create an infinite list of any datatype that supports Ord?

Answer 1

It might be a little easier to get away from the syntactic-sugary [a..b] stuff, and think about a simple function from the Prelude:

repeat :: a -> [a]
repeat x = x : repeat x

You should forget about evaluation for now and start thinking declaratively, i.e. think of the above like a function in mathematics which can be read:

"repeat x" means "x" consed with "repeat x"

Yes, "lazy evaluation" is what we call what allows us to express this, but ideally we'd really like to just forget about evaluation and think about what our code means. In imperative programming you are obligated to think about evaluation at all times.

Here is more or less what your [1..] desugars to:

enumFrom n = n : enumFrom (succ n)

and you can see in @tel's answer how the compiler goes about expanding that.

Answer 2

Haskell "creates" infinite lists because it doesn't create any elements until it needs to. For instance, let's walk through an expansion of head [1..] which results in 1 in Haskell and an infinite loop in strict languages.

head [1..]

===                                 [expand `head`, literally 
                                     just inline the definition]
case [1..] of
  []        -> error "empty list"
  (x : xs)  -> x

===                                 [evaluate [1..] one step,
                                     check if it matches the case]
case 1:[2..] of
  []        -> error "empty list"
  (x : xs)  -> x

===                                 [it does!]

(1 : [2..]) -> 1

===                                 [fin]

1

Note that this is pretty backward compared to most languages which would start by attacking the definition of [1..] instead of attacking head.

You can write [x..] not for any type in the Ord typeclass (which only lets us say whether two things are greater or lesser than one another) but instead for anything in the Enum typeclass as [x..] translates to enumFrom x where enumFrom :: Enum a => a -> [a].

Answer 3

The concept of infinite lists should be easy to understand for anyone coming from an object-oriented background.

The trick is to think about Haskell lists not as arrays or even linked lists, but as iterator objects. An iterator object is an object that has two methods, hasNext and getNext.

Normally, an iterator's hasNext would return False after a finite number of getNext invocations. That is certainly true if you consider iterators tied to "real" collections such as arrays, hash maps, files etc.

But nothing inherently forces an iterator to be "finite". You could implement an infinite iterator very easily. In Haskell-like pseudocode:

object Iterator where
  hasNext _ = True
  getNext = do
    state <- get
    put (state + 1)
    return state

If you didn't know how this iterator is actually implemented, just by observing its behaviour you'd think that it's tied to an infinite (or at least very huge) collection. But it is just that — an object that returns consecutive numbers.

Another similar analogy is special files in UNIX, such as /dev/zero or /dev/random. If they were tied to real files on your hard disk, the disk would have to be infinite. But they are not — instead the contents is generated on demand by the kernel, and you can demand as much of it as you like.

Haskell's lazy lists work exactly like that, except they also "buffer" all the produced values, so that you can examine them repeatedly without doing repeated evaluation.