Re: [Haskell-cafe] The values of infinite lists

On Wed, May 10, 2006 at 02:00:20PM +0900, Deokhwan Kim wrote:

To: haskell-cafe@haskell.org From: Deokhwan Kim Date: Wed, 10 May 2006 14:00:20 +0900 Subject: [Haskell-cafe] The values of infinite lists

Are the values of infinite lists _|_ (bottom)?

In section 1.3, the Haskell 98 report said as follows:

Errors in Haskell are semantically equivalent to _|_. Technically, they are not distinguishable from nontermination, so the language includes no mechanism for detecting or acting upon errors.

type theoreticians talk like that ;-). this paragraph is more about the "error" function than about infinite data structures. it means that whenever you trigger an "error ..." line, you make the program non-terminating, just like if you try to access the last element of an infinite list. the program still *ends* with an error message (notifying you that it won't *terminate*) because it is nice and it knows you don't like to wait forever. (-:

Therefore, the value of the following infinity is _|_. Right?

data Nat = Zero | Succ Nat

infinity = Succ infinity

same as with lists: as long as you don't get lost in an infinitely distant point in the data structure, you are fine: you can do this ghci> case infinity of Succ _ -> "not there yet."; Zero -> "the end." ghci> take 1000 [1..] actually one of the things that i still find most amazing about haskell is that i can express so many algorithms by starting from the declaration of an infinite data structure and then traversing a finite part of it. the king paper on graph algorithms in haskell has some nice examples on this, too. cheers, matthias