CODEWITHSUNDEEP
haskellstreamlazy-evaluationinfinite
Jack Brandt
Jack Brandt

Reputation: 87

Haskell Streams (Comonadic): Infinite?

I've seen streams used as the default example of a comonad, but I can't quite figure how they're infinite, but not.

Assume we have the data constructor (from here)

data Stream a = a :> Stream a

How do we finally finish off a stream? Do we write it w/ an undefined at the end? I get that the language is lazy, but somewhere the knot must be cut, right? Am I just wrong?

Upvotes: 1

Views: 476

Answers (1)

chepner
chepner

Reputation: 531055

A stream is inherently infinite; you can't create a finite stream. Compare Stream and List:

data List   a = Empty | a :  List a
data Stream a =         a :> Stream a

You can create a finite list because of Empty constructor; it is possible to create a List value without referring to another List value. A Stream value, on the other hand, can only be created by using another Stream value. Any time you pattern match on a Stream, you get a value of type a and another Stream value.

"Finishing" a stream simply means you stop pulling values from it, not that you ever reach the "end" of the stream.

In practice, this means you cannot instantiate a full stream in memory; you can only build it on-demand, typically by calling a function to generate remainder of the stream when pattern matching on the :> constructor.

Upvotes: 6

Related Questions