[Haskell-cafe] The values of infinite lists

[Matthias Fischmann]

On Wed, May 10, 2006 at 02:00:20PM +0900, Deokhwan Kim wrote:
> To: haskell-cafe at haskell.org
> From: Deokhwan Kim <dk at ropas.snu.ac.kr>
> 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20060510/f45e701f/attachment.bin